InnoDB中的B+树索引结构

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

[本文参考了2014年2月3日的innodb_ruby版本0.8.8.]

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. We’ll now look into how InnoDB logically structures its indexes, using some practical examples.

InnoDB的INDEX页面的物理结构在InnoDB索引页面的物理结构中已经描述过。现在我们将通过一些实际示例来了解InnoDB如何在逻辑上构建其索引。

An aside on terminology: B+Tree, root, leaf, and level

关于术语的一点说明：B+树、根、叶子和层级

InnoDB uses a B+Tree structure for its indexes. A B+Tree is particularly efficient when data doesn’t fit in memory and must be read from the disk, as it ensures that a fixed maximum number of reads would be required to access any data requested, based only on the depth of the tree, which scales nicely.

InnoDB使用B+树结构来进行索引。当数据无法放入内存并且必须从磁盘读取时，B+树特别高效，因为它确保只需要固定的最大读取次数来访问任何请求的数据，仅基于树的深度，这样可以很好地进行扩展。

An index tree starts at a “root” page, whose location is fixed (and permanently stored in the InnoDB’s data dictionary) as a starting point for accessing the tree. The tree may be as small as the single root page, or as large as many millions of pages in a multi-level tree.

索引树从一个“根”页面开始，其位置是固定的（并永久存储在InnoDB的数据字典中），作为访问树的起点。树可以只有一个根页面，也可以是一个多级树中的数百万个页面。

Pages are referred to as being “leaf” pages or “non-leaf” pages (also called “internal” or “node” pages in some contexts). Leaf pages contain actual row data. Non-leaf pages contain only pointers to other non-leaf pages, or to leaf pages. The tree is balanced, so all branches of the tree have the same depth.

页被称为“叶子”页或“非叶子”页（在某些上下文中也称为“内部”或“节点”页）。叶子...