索引

PG 使用的索引虽然它称之为B-Tree，但实际和 MySQL innoDB 的 B+树类似，中间层都不存数据，叶节点才存。不过它的叶结点也不是直接存数据，而是存储指向数据的指针。数据通过堆表来存储。它用的是非聚簇索引，数据和索引分开。这个结构实际上和 MySQL 里的 MySIAM 是类似的。

这个B树是基于《Lehman&Yao的高并发B树管理算法》实现的，相较于 innoDB 的 B+树，主要做了两点改变：

1. 中间层页节点增加左右指针，指向页面的右兄弟，组成链表

2. 每个页面中添加了 high key，表示该页面中key的最大值

当一个插入操作触发页分裂、另一个并发的查询操作也查到这页时，可能要查的数据已经被分裂走了。要避免这种情况，B+树 需要对父子页面加锁。而 Lehman&Yao 的B树通过如上两点改进，使得页分裂时一般无需加锁。

当一个查询操作沿着 downlink 到达子页面时，将页面的 high key 和 search key 进行比较，如果 search key > high key，说明这个页面正在进行并发分裂，沿着 right-link 向右找到包含查询范围的那个分裂出来的新页面即可。

67.4.1. B-Tree Structure

PostgreSQL B-Tree indexes are multi-level tree structures, where each level of the tree can be used as a doubly-linked list of pages. A single metapage is stored in a fixed position at the start of the first segment file of the index. All other pages are either leaf pages or internal pages. Leaf pages are the pages on the lowest level of the tree. All other levels consist of internal pages. Each leaf page contains tuples that point to table rows. Each internal page contains tuples that point to the next level down in the tree. Typically, over 99% of all pages are leaf pages. Both internal pages and leaf pages use the standard page format described in Section 73.6.

Chapter 67. B-Tree Indexes

PostgreSQL Blink-tree ReadMe---翻译