高效遍历InnoDB B+树与页面目录

[This post refers to innodb_ruby version 0.8.8 as of February 3, 2014.]

In On learning InnoDB: A journey to the core, I introduced the innodb_diagrams project to document the InnoDB internals, which provides the diagrams used in this post. Later on in A quick introduction to innodb_ruby I walked through installation and a few quick demos of the innodb_space command-line tool.

在On learning InnoDB: A journey to the core中，我介绍了innodb_diagrams项目，用于记录InnoDB内部结构，该项目提供了本文中使用的图表。稍后在A quick introduction to innodb_ruby中，我介绍了安装和使用innodb_space命令行工具的一些快速演示。

The physical structure of InnoDB’s INDEX pages was described in The physical structure of InnoDB index pages, and the logical structure was described in B+Tree index structures in InnoDB, and the physical structure of records was described in The physical structure of records in InnoDB. Now we’ll look in detail at the “page directory” structure that has been seen several times already, but not yet described.

InnoDB的INDEX页面的物理结构在InnoDB索引页面的物理结构中有所描述，逻辑结构在InnoDB中的B+Tree索引结构中有所描述，记录的物理结构在InnoDB中记录的物理结构中有所描述。现在我们将详细介绍已经多次出现但尚未描述的“页面目录”结构。

In this post, only COMPACT row format (for Barracuda table format) is considered.

在本文中，仅考虑COMPACT行格式（用于Barracuda表格式）。

The purpose of the page directory

页面目录的目的

As described in the posts mentioned above, all records in INDEX pages are linked together in a singly-linked list in ascending order. However, list traversal through a page with potentially several hundred records in it is very expensive: every record’s key must be compared, and this needs to be done at each level of the B+Tree until the record sought is found on a leaf page.

如上述帖子所述，INDEX页面中的所有记录按升序链接在一起形成单链表。然而，通过可能包含几百条记录的页面进行列表遍历非常昂贵：必须比较每个记录的键，并且这需要在B+Tree的每个级别上进行，直到在叶子页面上找到所需的记录。

The page directory greatly optimizes this search by providing a fixed-width data structure with direct pointers to 1 of every 4-8 records, in order. Thus, it can be used for a traditional binary search of the records in each page, starti...