列的顺序
当使用多列索引时与列的顺序有关的问题会显示出来。对于B-tree，这个顺序非常重要：页中的数据先以第一个字段进行排序，然后再第二个字段，以此类推。
下图是在range和model列上构建的索引：
当然，上图这么小的索引在一个root页足以存放。但是为了清晰起见，特意将其分成几页。
从图中可见，通过类似的谓词class = 3（仅按第一个字段进行搜索）或者class = 3 and model = 'Boeing 777-300'（按两个字段进行搜索）将非常高效。
然而，通过谓词model = 'Boeing 777-300'进行搜索的效率将大大降低：从root开始，判断不出选择哪个子节点进行向下搜索，因此会遍历所有子节点向下进行搜索。这并不意味着永远无法使用这样的索引----它的效率有问题。例如，如果aircraft有3个classes值，每个class类中有许多model值，此时不得不扫描索引1/3的数据，这可能比全表扫描更有效。
但是，当创建如下索引时：
1. demo=# create index on aircrafts( 2. model, 3. (case when range < 4000 then 1 when range < 10000 then 2 else 3 end));
索引字段的顺序会改变：
通过这个索引，model = 'Boeing 777-300'将会很有效，但class = 3则没这么高效。
NULLs
PostgreSQL的B-tree支持在NULLs上创建索引，可以通过IS NULL或者IS NOT NULL的条件进行查询。
考虑flights表，允许NULLs：
1. demo=# create index on flights(actual_arrival); 2. demo=# explain(costs off) select * from flights where actual_arrival is null; 3. QUERY PLAN 4. ------------------------------------------------------- 5. Bitmap Heap Scan on flights 6. Recheck Cond: (actual_arrival IS NULL) 7. -> Bitmap Index Scan on flights_actual_arrival_idx 8. Index Cond: (actual_arrival IS NULL) 9. (4 rows)
NULLs位于叶子节点的一端或另一端，这依赖于索引的创建方式（NULLS FIRST或NULLS LAST）。如果查询中包含排序，这就显得很重要了：如果SELECT语句在ORDER BY子句中指定NULLs的顺序索引构建的顺序一样（NULLS FIRST或NULLS LAST），就可以使用整个索引。
下面的例子中，他们的顺序相同，因此可以使用索引：
1. demo=# explain(costs off) 2. select * from flights order by actual_arrival NULLS LAST; 3. QUERY PLAN 4. -------------------------------------------------------- 5. Index Scan using flights_actual_arrival_idx on flights 6. (1 row)
下面的例子，顺序不同，优化器选择顺序扫描然后进行排序：
1. demo=# explain(costs off) 2. select * from flights order by actual_arrival NULLS FIRST; 3. QUERY PLAN 4. ---------------------------------------- 5. Sort 6. Sort Key: actual_arrival NULLS FIRST 7. -> Seq Scan on flights 8. (3 rows)
NULLs必须位于开头才能使用索引：
1. demo=# create index flights_nulls_first_idx on flights(actual_arrival NULLS FIRST); 2. demo=# explain(costs off) 3. select * from flights order by actual_arrival NULLS FIRST; 4. QUERY PLAN 5. ----------------------------------------------------- 6. Index Scan using flights_nulls_first_idx on flights 7. (1 row)
像这样的问题是由NULLs引起的而不是无法排序，也就是说NULL和其他这比较的结果无法预知：
1. demo=# \pset null NULL 2. demo=# select null < 42; 3. ?column? 4. ---------- 5. NULL 6. (1 row)
这和B-tree的概念背道而驰并且不符合一般的模式。然而NULLs在数据库中扮演者很重要的角色，因此不得不为NULL做特殊设置。
由于NULLs可以被索引，因此即使表上没有任何标记也可以使用索引。（因为这个索引包含表航记录的所有信息）。如果查询需要排序的数据，而且索引确保了所需的顺序，那么这可能是由意义的。这种情况下，查询计划更倾向于通过索引获取数据。
属性
下面介绍btree访问方法的特性。
1. amname | name | pg_indexam_has_property 2. --------+---------------+------------------------- 3. btree | can_order | t 4. btree | can_unique | t 5. btree | can_multi_col | t 6. btree | can_exclude | t
可以看到，B-tree能够排序数据并且支持唯一性。同时还支持多列索引，但是其他访问方法也支持这种索引。我们将在下次讨论EXCLUDE条件。
1. name | pg_index_has_property 2. ---------------+----------------------- 3. clusterable | t 4. index_scan | t 5. bitmap_scan | t 6. backward_scan | t
Btree访问方法可以通过以下两种方式获取数据：index scan以及bitmap scan。可以看到，通过tree可以向前和向后进行遍历。
1. name | pg_index_column_has_property 2. --------------------+------------------------------ 3. asc | t 4. desc | f 5. nulls_first | f 6. nulls_last | t 7. orderable | t 8. distance_orderable | f 9. returnable | t 10. search_array | t 11. search_nulls | t
前四种特性指定了特定列如何精确的排序。本案例中，值以升序（asc）进行排序并且NULLs在后面（nulls_last）。也可以有其他组合。
search_array的特性支持向这样的表达式：
1. demo=# explain(costs off) 2. select * from aircrafts where aircraft_code in ('733','763','773'); 3. QUERY PLAN 4. ----------------------------------------------------------------- 5. Index Scan using aircrafts_pkey on aircrafts 6. Index Cond: (aircraft_code = ANY ('{733,763,773}'::bpchar[])) 7. (2 rows)
returnable属性支持index-only scan，由于索引本身也存储索引值所以这是合理的。下面简单介绍基于B-tree的覆盖索引。
具有额外列的唯一索引
前面讨论了：覆盖索引包含查询所需的所有值，需不要再回表。唯一索引可以成为覆盖索引。
假设我们查询所需要的列添加到唯一索引，新的组合唯一键可能不再唯一，同一列上将需要2个索引：一个唯一，支持完整性约束；另一个是非唯一，为了覆盖索引。这当然是低效的。
在我们公司 Anastasiya Lubennikova @ lubennikovaav 改进了btree，额外的非唯一列可以包含在唯一索引中。我们希望这个补丁可以被社区采纳。实际上PostgreSQL11已经合了该补丁。
考虑表bookings：d
1. demo=# \d bookings 2. Table "bookings.bookings" 3. Column | Type | Modifiers 4. --------------+--------------------------+----------- 5. book_ref | character(6) | not null 6. book_date | timestamp with time zone | not null 7. total_amount | numeric(10,2) | not null 8. Indexes: 9. "bookings_pkey" PRIMARY KEY, btree (book_ref) 10. Referenced by: 11. 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);
然后使用新索引替代现有索引：
1. demo=# begin; 2. demo=# alter table bookings drop constraint bookings_pkey cascade; 3. demo=# alter table bookings add primary key using index bookings_pkey2; 4. demo=# alter table tickets add foreign key (book_ref) references bookings (book_ref); 5. demo=# commit;
然后表结构：
1. demo=# \d bookings 2. Table "bookings.bookings" 3. Column | Type | Modifiers 4. --------------+--------------------------+----------- 5. book_ref | character(6) | not null 6. book_date | timestamp with time zone | not null 7. total_amount | numeric(10,2) | not null 8. Indexes: 9. "bookings_pkey2" PRIMARY KEY, btree (book_ref) INCLUDE (book_date) 10. Referenced by: 11. TABLE "tickets" CONSTRAINT "tickets_book_ref_fkey" FOREIGN KEY (book_ref) REFERENCES bookings(book_ref)
此时，这个索引可以作为唯一索引工作也可以作为覆盖索引：
1. demo=# explain(costs off) 2. select book_ref, book_date from bookings where book_ref = '059FC4'; 3. QUERY PLAN 4. -------------------------------------------------- 5. Index Only Scan using bookings_pkey2 on bookings 6. Index Cond: (book_ref = '059FC4'::bpchar) 7. (2 rows)
创建索引
众所周知，对于大表，加载数据时最好不要带索引；加载完成后再创建索引。这样做不仅提升效率还能节省空间。
创建B-tree索引比向索引中插入数据更高效。所有的数据大致上都已排序，并且数据的叶子页已创建好，然后只需构建内部页直到root页构建成一个完整的B-tree。
这种方法的速度依赖于RAM的大小，受限于参数maintenance_work_mem。因此增大该参数值可以提升速度。对于唯一索引，除了分配maintenance_work_mem的内存外，还分配了work_mem的大小的内存。
比较
前面，提到PG需要知道对于不同类型的值调用哪个函数，并且这个关联方法存储在哈希访问方法中。同样，系统必须找出如何排序。这在排序、分组（有时）、merge join中会涉及。PG不会将自身绑定到操作符名称，因为用户可以自定义他们的数据类型并给出对应不同的操作符名称。
例如bool_ops操作符集中的比较操作符：
1. postgres=# select amop.amopopr::regoperator as opfamily_operator, 2. amop.amopstrategy 3. from pg_am am, 4. pg_opfamily opf, 5. pg_amop amop 6. where opf.opfmethod = am.oid 7. and amop.amopfamily = opf.oid 8. and am.amname = 'btree' 9. and opf.opfname = 'bool_ops' 10. order by amopstrategy; 11. opfamily_operator | amopstrategy 12. ---------------------+-------------- 13. <(boolean,boolean) | 1 14. <=(boolean,boolean) | 2 15. =(boolean,boolean) | 3 16. >=(boolean,boolean) | 4 17. >(boolean,boolean) | 5 18. (5 rows)
这里可以看到有5种操作符，但是不应该依赖于他们的名字。为了指定哪种操作符做什么操作，引入策略的概念。为了描述操作符语义，定义了5种策略：
1 — less
2 — less or equal
3 — equal
4 — greater or equal
5 — greater
1. postgres=# select amop.amopopr::regoperator as opfamily_operator 2. from pg_am am, 3. pg_opfamily opf, 4. pg_amop amop 5. where opf.opfmethod = am.oid 6. and amop.amopfamily = opf.oid 7. and am.amname = 'btree' 8. and opf.opfname = 'integer_ops' 9. and amop.amopstrategy = 1 10. order by opfamily_operator; 11. pfamily_operator 12. ---------------------- 13. <(integer,bigint) 14. <(smallint,smallint) 15. <(integer,integer) 16. <(bigint,bigint) 17. <(bigint,integer) 18. <(smallint,integer) 19. <(integer,smallint) 20. <(smallint,bigint) 21. <(bigint,smallint) 22. (9 rows) 23.
一些操作符族可以包含几种操作符，例如integer_ops包含策略1的几种操作符：
正因如此，当比较类型在一个操作符族中时，不同类型值的比较，优化器可以避免类型转换。
索引支持的新数据类型
文档中提供了一个创建符合数值的新数据类型，以及对这种类型数据进行排序的操作符类。该案例使用C语言完成。但不妨碍我们使用纯SQL进行对比试验。
创建一个新的组合类型：包含real和imaginary两个字段
postgres=# create type complex as (re float, im float);
创建一个包含该新组合类型字段的表：
1. postgres=# create table numbers(x complex); 2. postgres=# insert into numbers values ((0.0, 10.0)), ((1.0, 3.0)), ((1.0, 1.0));
现在有个疑问，如果在数学上没有为他们定义顺序关系，如何进行排序？
已经定义好了比较运算符：
1. postgres=# select * from numbers order by x; 2. x 3. -------- 4. (0,10) 5. (1,1) 6. (1,3) 7. (3 rows)
默认情况下，对于组合类型排序是分开的：首先比较第一个字段然后第二个字段，与文本字符串比较方法大致相同。但是我们也可以定义其他的排序方式，例如组合数字可以当做一个向量，通过模值进行排序。为了定义这样的顺序，我们需要创建一个函数：
1. postgres=# create function modulus(a complex) returns float as $$ 2. select sqrt(a.re*a.re + a.im*a.im); 3. $$ immutable language sql; 4. 5. 6. //此时，使用整个函数系统的定义5种操作符： 7. postgres=# create function complex_lt(a complex, b complex) returns boolean as $$ 8. select modulus(a) < modulus(b); 9. $$ immutable language sql; 10. 11. postgres=# create function complex_le(a complex, b complex) returns boolean as $$ 12. select modulus(a) <= modulus(b); 13. $$ immutable language sql; 14. 15. postgres=# create function complex_eq(a complex, b complex) returns boolean as $$ 16. select modulus(a) = modulus(b); 17. $$ immutable language sql; 18. 19. postgres=# create function complex_ge(a complex, b complex) returns boolean as $$ 20. select modulus(a) >= modulus(b); 21. $$ immutable language sql; 22. 23. postgres=# create function complex_gt(a complex, b complex) returns boolean as $$ 24. select modulus(a) > modulus(b); 25. $$ immutable language sql;
然后创建对应的操作符：
1. postgres=# create operator #<#(leftarg=complex, rightarg=complex, procedure=complex_lt); 2. postgres=# create operator #<=#(leftarg=complex, rightarg=complex, procedure=complex_le); 3. postgres=# create operator #=#(leftarg=complex, rightarg=complex, procedure=complex_eq); 4. postgres=# create operator #>=#(leftarg=complex, rightarg=complex, procedure=complex_ge); 5. postgres=# create operator #>#(leftarg=complex, rightarg=complex, procedure=complex_gt);
此时，可以比较数字：
1. postgres=# select (1.0,1.0)::complex #<# (1.0,3.0)::complex; 2. ?column? 3. ---------- 4. t 5. (1 row)
除了整个5个操作符，还需要定义函数：小于返回-1；等于返回0；大于返回1。其他访问方法可能需要定义其他函数：
1. postgres=# create function complex_cmp(a complex, b complex) returns integer as $$ 2. select case when modulus(a) < modulus(b) then -1 3. when modulus(a) > modulus(b) then 1 4. else 0 5. end; 6. $$ language sql;
创建一个操作符类：
1. postgres=# create operator class complex_ops 2. default for type complex 3. using btree as 4. operator 1 #<#, 5. operator 2 #<=#, 6. operator 3 #=#, 7. operator 4 #>=#, 8. operator 5 #>#, 9. function 1 complex_cmp(complex,complex); 10. 11. //排序结果： 12. postgres=# select * from numbers order by x; 13. x 14. -------- 15. (1,1) 16. (1,3) 17. (0,10) 18. (3 rows) 19. 20. //可以使用此查询获取支持的函数： 21. 22. postgres=# select amp.amprocnum, 23. amp.amproc, 24. amp.amproclefttype::regtype, 25. amp.amprocrighttype::regtype 26. from pg_opfamily opf, 27. pg_am am, 28. pg_amproc amp 29. where opf.opfname = 'complex_ops' 30. and opf.opfmethod = am.oid 31. and am.amname = 'btree' 32. and amp.amprocfamily = opf.oid; 33. amprocnum | amproc | amproclefttype | amprocrighttype 34. -----------+-------------+----------------+----------------- 35. 1 | complex_cmp | complex | complex 36. (1 row)
内部结构
使用pageinspect插件观察B-tree结构：
demo=# create extension pageinspect;
索引的元数据页：
1. demo=# select * from bt_metap('ticket_flights_pkey'); 2. magic | version | root | level | fastroot | fastlevel 3. --------+---------+------+-------+----------+----------- 4. 340322 | 2 | 164 | 2 | 164 | 2 5. (1 row)
值得关注的是索引level：不包括root，有一百万行记录的表其索引只需要2层就可以了。
Root页，即164号页面的统计信息：
1. demo=# select type, live_items, dead_items, avg_item_size, page_size, free_size 2. from bt_page_stats('ticket_flights_pkey',164); 3. type | live_items | dead_items | avg_item_size | page_size | free_size 4. ------+------------+------------+---------------+-----------+----------- 5. r | 33 | 0 | 31 | 8192 | 6984 6. (1 row)
该页中数据：
1. demo=# select itemoffset, ctid, itemlen, left(data,56) as data 2. from bt_page_items('ticket_flights_pkey',164) limit 5; 3. itemoffset | ctid | itemlen | data 4. ------------+---------+---------+---------------------------------------------------------- 5. 1 | (3,1) | 8 | 6. 2 | (163,1) | 32 | 1d 30 30 30 35 34 33 32 33 30 35 37 37 31 00 00 ff 5f 00 7. 3 | (323,1) | 32 | 1d 30 30 30 35 34 33 32 34 32 33 36 36 32 00 00 4f 78 00 8. 4 | (482,1) | 32 | 1d 30 30 30 35 34 33 32 35 33 30 38 39 33 00 00 4d 1e 00 9. 5 | (641,1) | 32 | 1d 30 30 30 35 34 33 32 36 35 35 37 38 35 00 00 2b 09 00 10. (5 rows)
第一个tuple指定该页的最大值，真正的数据从第二个tuple开始。很明显最左边子节点的页号是163，然后是323。反过来，可以使用相同的函数搜索。
PG10版本提供了"amcheck"插件，该插件可以检测B-tree数据的逻辑一致性，使我们提前探知故障。
