PostgreSQL的B-tree索引用法详解

demo=# select * from aircrafts;
 aircraft_code |  model  | range
---------------+---------------------+-------
 773   | Boeing 777-300  | 11100
 763   | Boeing 767-300  | 7900
 SU9   | Sukhoi SuperJet-100 | 3000
 320   | Airbus A320-200  | 5700
 321   | Airbus A321-200  | 5600
 319   | Airbus A319-100  | 6700
 733   | Boeing 737-300  | 4200
 CN1   | Cessna 208 Caravan | 1200
 CR2   | Bombardier CRJ-200 | 2700
(9 rows)
demo=# create index on aircrafts(range);
demo=# set enable_seqscan = off;

demo=# explain(costs off) select * from aircrafts where range = 3000;
     QUERY PLAN      
---------------------------------------------------
 Index Scan using aircrafts_range_idx on aircrafts
 Index Cond: (range = 3000)
(2 rows)

demo=# explain(costs off) select * from aircrafts where range < 3000;
     QUERY PLAN     
---------------------------------------------------
 Index Scan using aircrafts_range_idx on aircrafts
 Index Cond: (range < 3000)
(2 rows)

demo=# explain(costs off) select * from aircrafts
where range between 3000 and 5000;
      QUERY PLAN      
-----------------------------------------------------
 Index Scan using aircrafts_range_idx on aircrafts
 Index Cond: ((range >= 3000) AND (range <= 5000))
(2 rows)

demo=# create index on aircrafts(range desc);

demo=# create view aircrafts_v as
select model,
  case
   when range < 4000 then 1
   when range < 10000 then 2
   else 3
  end as class
from aircrafts; 
 
demo=# select * from aircrafts_v;
  model  | class
---------------------+-------
 Boeing 777-300  |  3
 Boeing 767-300  |  2
 Sukhoi SuperJet-100 |  1
 Airbus A320-200  |  2
 Airbus A321-200  |  2
 Airbus A319-100  |  2
 Boeing 737-300  |  2
 Cessna 208 Caravan |  1
 Bombardier CRJ-200 |  1
(9 rows)

demo=# create index on aircrafts(
 (case when range < 4000 then 1 when range < 10000 then 2 else 3 end),
 model);

demo=# select class, model from aircrafts_v order by class, model;
 class |  model  
-------+---------------------
  1 | Bombardier CRJ-200
  1 | Cessna 208 Caravan
  1 | Sukhoi SuperJet-100
  2 | Airbus A319-100
  2 | Airbus A320-200
  2 | Airbus A321-200
  2 | Boeing 737-300
  2 | Boeing 767-300
  3 | Boeing 777-300
(9 rows) 
 
demo=# explain(costs off)
select class, model from aircrafts_v order by class, model;
      QUERY PLAN      
--------------------------------------------------------
 Index Scan using aircrafts_case_model_idx on aircrafts
(1 row)

demo=# select class, model from aircrafts_v order by class desc, model desc;
 class |  model  
-------+---------------------
  3 | Boeing 777-300
  2 | Boeing 767-300
  2 | Boeing 737-300
  2 | Airbus A321-200
  2 | Airbus A320-200
  2 | Airbus A319-100
  1 | Sukhoi SuperJet-100
  1 | Cessna 208 Caravan
  1 | Bombardier CRJ-200
(9 rows)
demo=# explain(costs off)
select class, model from aircrafts_v order by class desc, model desc;
       QUERY PLAN       
-----------------------------------------------------------------
 Index Scan BACKWARD using aircrafts_case_model_idx on aircrafts
(1 row)

demo=# explain(costs off)
select class, model from aircrafts_v order by class ASC, model DESC;
     QUERY PLAN     
-------------------------------------------------
 Sort
 Sort Key: (CASE ... END), aircrafts.model DESC
 -> Seq Scan on aircrafts
(3 rows)

demo=# create index aircrafts_case_asc_model_desc_idx on aircrafts(
 (case
 when range < 4000 then 1
 when range < 10000 then 2
 else 3
 end) ASC,
 model DESC); 
 
demo=# explain(costs off)
select class, model from aircrafts_v order by class ASC, model DESC;
       QUERY PLAN       
-----------------------------------------------------------------
 Index Scan using aircrafts_case_asc_model_desc_idx on aircrafts
(1 row)

demo=# create index on aircrafts(
 model,
 (case when range < 4000 then 1 when range < 10000 then 2 else 3 end));

demo=# create index on flights(actual_arrival);
demo=# explain(costs off) select * from flights where actual_arrival is null;
      QUERY PLAN      
-------------------------------------------------------
 Bitmap Heap Scan on flights
 Recheck Cond: (actual_arrival IS NULL)
 -> Bitmap Index Scan on flights_actual_arrival_idx
   Index Cond: (actual_arrival IS NULL)
(4 rows)

demo=# explain(costs off)
select * from flights order by actual_arrival NULLS LAST;
      QUERY PLAN      
--------------------------------------------------------
 Index Scan using flights_actual_arrival_idx on flights
(1 row)

demo=# explain(costs off)
select * from flights order by actual_arrival NULLS FIRST;
    QUERY PLAN    
----------------------------------------
 Sort
 Sort Key: actual_arrival NULLS FIRST
 -> Seq Scan on flights
(3 rows)

demo=# create index flights_nulls_first_idx on flights(actual_arrival NULLS FIRST);
demo=# explain(costs off)
select * from flights order by actual_arrival NULLS FIRST;
      QUERY PLAN      
-----------------------------------------------------
 Index Scan using flights_nulls_first_idx on flights
(1 row)

demo=# \pset null NULL
demo=# select null < 42;
 "htmlcode">

 amname |  name  | pg_indexam_has_property
--------+---------------+-------------------------
 btree | can_order  | t
 btree | can_unique | t
 btree | can_multi_col | t
 btree | can_exclude | t


可以看到，B-tree能够排序数据并且支持唯一性。同时还支持多列索引，但是其他访问方法也支持这种索引。我们将在下次讨论EXCLUDE条件。


  name  | pg_index_has_property
---------------+-----------------------
 clusterable | t
 index_scan | t
 bitmap_scan | t
 backward_scan | t


Btree访问方法可以通过以下两种方式获取数据：index scan以及bitmap scan。可以看到，通过tree可以向前和向后进行遍历。


  name   | pg_index_column_has_property
--------------------+------------------------------
 asc    | t
 desc    | f
 nulls_first  | f
 nulls_last   | t
 orderable   | t
 distance_orderable | f
 returnable   | t
 search_array  | t
 search_nulls  | t


前四种特性指定了特定列如何精确的排序。本案例中，值以升序（asc）进行排序并且NULLs在后面（nulls_last）。也可以有其他组合。
search_array的特性支持向这样的表达式：


demo=# explain(costs off)
select * from aircrafts where aircraft_code in ('733','763','773');
       QUERY PLAN       
-----------------------------------------------------------------
 Index Scan using aircrafts_pkey on aircrafts
 Index Cond: (aircraft_code = ANY ('{733,763,773}'::bpchar[]))
(2 rows)


returnable属性支持index-only scan，由于索引本身也存储索引值所以这是合理的。下面简单介绍基于B-tree的覆盖索引。
具有额外列的唯一索引
前面讨论了：覆盖索引包含查询所需的所有值，需不要再回表。唯一索引可以成为覆盖索引。
假设我们查询所需要的列添加到唯一索引，新的组合唯一键可能不再唯一，同一列上将需要2个索引：一个唯一，支持完整性约束；另一个是非唯一，为了覆盖索引。这当然是低效的。
在我们公司 Anastasiya Lubennikova @ lubennikovaav 改进了btree，额外的非唯一列可以包含在唯一索引中。我们希望这个补丁可以被社区采纳。实际上PostgreSQL11已经合了该补丁。
考虑表bookings：d


demo=# \d bookings
    Table "bookings.bookings"
 Column |   Type   | Modifiers
--------------+--------------------------+-----------
 book_ref  | character(6)    | not null
 book_date | timestamp with time zone | not null
 total_amount | numeric(10,2)   | not null
Indexes:
 "bookings_pkey" PRIMARY KEY, btree (book_ref)
Referenced by:
TABLE "tickets" CONSTRAINT "tickets_book_ref_fkey" FOREIGN KEY (book_ref) REFERENCES bookings(book_ref)


这个表中，主键（book_ref,booking code）通过常规的btree索引提供，下面创建一个由额外列的唯一索引：


demo=# create unique index bookings_pkey2 on bookings(book_ref) INCLUDE (book_date);


然后使用新索引替代现有索引：


demo=# begin;
demo=# alter table bookings drop constraint bookings_pkey cascade;
demo=# alter table bookings add primary key using index bookings_pkey2;
demo=# alter table tickets add foreign key (book_ref) references bookings (book_ref);
demo=# commit;


然后表结构：


demo=# \d bookings
    Table "bookings.bookings"
 Column |   Type   | Modifiers
--------------+--------------------------+-----------
 book_ref  | character(6)    | not null
 book_date | timestamp with time zone | not null
 total_amount | numeric(10,2)   | not null
Indexes:
 "bookings_pkey2" PRIMARY KEY, btree (book_ref) INCLUDE (book_date)
Referenced by:
TABLE "tickets" CONSTRAINT "tickets_book_ref_fkey" FOREIGN KEY (book_ref) REFERENCES bookings(book_ref)


此时，这个索引可以作为唯一索引工作也可以作为覆盖索引：


demo=# explain(costs off)
select book_ref, book_date from bookings where book_ref = '059FC4';
     QUERY PLAN     
--------------------------------------------------
 Index Only Scan using bookings_pkey2 on bookings
 Index Cond: (book_ref = '059FC4'::bpchar)
(2 rows)


创建索引
众所周知，对于大表，加载数据时最好不要带索引；加载完成后再创建索引。这样做不仅提升效率还能节省空间。
创建B-tree索引比向索引中插入数据更高效。所有的数据大致上都已排序，并且数据的叶子页已创建好，然后只需构建内部页直到root页构建成一个完整的B-tree。
这种方法的速度依赖于RAM的大小，受限于参数maintenance_work_mem。因此增大该参数值可以提升速度。对于唯一索引，除了分配maintenance_work_mem的内存外，还分配了work_mem的大小的内存。
比较
前面，提到PG需要知道对于不同类型的值调用哪个函数，并且这个关联方法存储在哈希访问方法中。同样，系统必须找出如何排序。这在排序、分组（有时）、merge join中会涉及。PG不会将自身绑定到操作符名称，因为用户可以自定义他们的数据类型并给出对应不同的操作符名称。
例如bool_ops操作符集中的比较操作符：


postgres=# select amop.amopopr::regoperator as opfamily_operator,
   amop.amopstrategy
from  pg_am am,
   pg_opfamily opf,
   pg_amop amop
where opf.opfmethod = am.oid
and  amop.amopfamily = opf.oid
and  am.amname = 'btree'
and  opf.opfname = 'bool_ops'
order by amopstrategy;
 opfamily_operator | amopstrategy
---------------------+--------------
 <(boolean,boolean) |   1
 <=(boolean,boolean) |   2
 =(boolean,boolean) |   3
 >=(boolean,boolean) |   4
 >(boolean,boolean) |   5
(5 rows)


这里可以看到有5种操作符，但是不应该依赖于他们的名字。为了指定哪种操作符做什么操作，引入策略的概念。为了描述操作符语义，定义了5种策略：
1 — less
2 — less or equal
3 — equal
4 — greater or equal
5 — greater


postgres=# select amop.amopopr::regoperator as opfamily_operator
from  pg_am am,
   pg_opfamily opf,
   pg_amop amop
where opf.opfmethod = am.oid
and  amop.amopfamily = opf.oid
and  am.amname = 'btree'
and  opf.opfname = 'integer_ops'
and  amop.amopstrategy = 1
order by opfamily_operator;
 pfamily_operator 
----------------------
 <(integer,bigint)
 <(smallint,smallint)
 <(integer,integer)
 <(bigint,bigint)
 <(bigint,integer)
 <(smallint,integer)
 <(integer,smallint)
 <(smallint,bigint)
 <(bigint,smallint)
(9 rows)



一些操作符族可以包含几种操作符，例如integer_ops包含策略1的几种操作符：
正因如此，当比较类型在一个操作符族中时，不同类型值的比较，优化器可以避免类型转换。
索引支持的新数据类型
文档中提供了一个创建符合数值的新数据类型，以及对这种类型数据进行排序的操作符类。该案例使用C语言完成。但不妨碍我们使用纯SQL进行对比试验。
创建一个新的组合类型：包含real和imaginary两个字段


postgres=# create type complex as (re float, im float);


创建一个包含该新组合类型字段的表：


postgres=# create table numbers(x complex);
postgres=# insert into numbers values ((0.0, 10.0)), ((1.0, 3.0)), ((1.0, 1.0));


现在有个疑问，如果在数学上没有为他们定义顺序关系，如何进行排序？
已经定义好了比较运算符：


postgres=# select * from numbers order by x;
 x 
--------
 (0,10)
 (1,1)
 (1,3)
(3 rows)


默认情况下，对于组合类型排序是分开的：首先比较第一个字段然后第二个字段，与文本字符串比较方法大致相同。但是我们也可以定义其他的排序方式，例如组合数字可以当做一个向量，通过模值进行排序。为了定义这样的顺序，我们需要创建一个函数：


postgres=# create function modulus(a complex) returns float as $$
 select sqrt(a.re*a.re + a.im*a.im);
$$ immutable language sql;
 
 
//此时，使用整个函数系统的定义5种操作符：
postgres=# create function complex_lt(a complex, b complex) returns boolean as $$
 select modulus(a) < modulus(b);
$$ immutable language sql;
 
postgres=# create function complex_le(a complex, b complex) returns boolean as $$
 select modulus(a) <= modulus(b);
$$ immutable language sql;
 
postgres=# create function complex_eq(a complex, b complex) returns boolean as $$
 select modulus(a) = modulus(b);
$$ immutable language sql;
 
postgres=# create function complex_ge(a complex, b complex) returns boolean as $$
 select modulus(a) >= modulus(b);
$$ immutable language sql;
 
postgres=# create function complex_gt(a complex, b complex) returns boolean as $$
 select modulus(a) > modulus(b);
$$ immutable language sql;


然后创建对应的操作符：


postgres=# create operator #<#(leftarg=complex, rightarg=complex, procedure=complex_lt);
postgres=# create operator #<=#(leftarg=complex, rightarg=complex, procedure=complex_le);
postgres=# create operator #=#(leftarg=complex, rightarg=complex, procedure=complex_eq);
postgres=# create operator #>=#(leftarg=complex, rightarg=complex, procedure=complex_ge);
postgres=# create operator #>#(leftarg=complex, rightarg=complex, procedure=complex_gt);


此时，可以比较数字：


postgres=# select (1.0,1.0)::complex #<# (1.0,3.0)::complex;
 "htmlcode">

postgres=# create function complex_cmp(a complex, b complex) returns integer as $$
 select case when modulus(a) < modulus(b) then -1
    when modulus(a) > modulus(b) then 1
    else 0
   end;
$$ language sql;


创建一个操作符类：


postgres=# create operator class complex_ops
default for type complex
using btree as
 operator 1 #<#,
 operator 2 #<=#,
 operator 3 #=#,
 operator 4 #>=#,
 operator 5 #>#,
function 1 complex_cmp(complex,complex);
 
//排序结果：
postgres=# select * from numbers order by x;
 x 
--------
 (1,1)
 (1,3)
 (0,10)
(3 rows)
 
//可以使用此查询获取支持的函数：
 
postgres=# select amp.amprocnum,
  amp.amproc,
  amp.amproclefttype::regtype,
  amp.amprocrighttype::regtype
from pg_opfamily opf,
  pg_am am,
  pg_amproc amp
where opf.opfname = 'complex_ops'
and opf.opfmethod = am.oid
and am.amname = 'btree'
and amp.amprocfamily = opf.oid;
 amprocnum | amproc | amproclefttype | amprocrighttype
-----------+-------------+----------------+-----------------
   1 | complex_cmp | complex  | complex
(1 row)


内部结构
使用pageinspect插件观察B-tree结构：


demo=# create extension pageinspect;


索引的元数据页：


demo=# select * from bt_metap('ticket_flights_pkey');
 magic | version | root | level | fastroot | fastlevel
--------+---------+------+-------+----------+-----------
 340322 |  2 | 164 |  2 |  164 |   2
(1 row)


值得关注的是索引level：不包括root，有一百万行记录的表其索引只需要2层就可以了。
Root页，即164号页面的统计信息：


demo=# select type, live_items, dead_items, avg_item_size, page_size, free_size
from bt_page_stats('ticket_flights_pkey',164);
 type | live_items | dead_items | avg_item_size | page_size | free_size
------+------------+------------+---------------+-----------+-----------
 r |   33 |   0 |   31 |  8192 |  6984
(1 row)


该页中数据：


demo=# select itemoffset, ctid, itemlen, left(data,56) as data
from bt_page_items('ticket_flights_pkey',164) limit 5;
 itemoffset | ctid | itemlen |       data       
------------+---------+---------+----------------------------------------------------------
   1 | (3,1) |  8 |
   2 | (163,1) |  32 | 1d 30 30 30 35 34 33 32 33 30 35 37 37 31 00 00 ff 5f 00
   3 | (323,1) |  32 | 1d 30 30 30 35 34 33 32 34 32 33 36 36 32 00 00 4f 78 00
   4 | (482,1) |  32 | 1d 30 30 30 35 34 33 32 35 33 30 38 39 33 00 00 4d 1e 00
   5 | (641,1) |  32 | 1d 30 30 30 35 34 33 32 36 35 35 37 38 35 00 00 2b 09 00
(5 rows)


第一个tuple指定该页的最大值，真正的数据从第二个tuple开始。很明显最左边子节点的页号是163，然后是323。反过来，可以使用相同的函数搜索。
PG10版本提供了"amcheck"插件，该插件可以检测B-tree数据的逻辑一致性，使我们提前探知故障。
以上为个人经验，希望能给大家一个参考，也希望大家多多支持。如有错误或未考虑完全的地方，望不吝赐教。