概念

一个Index就是一个B+Tree。
方方面面看：https://www.slideshare.net/ovaistariq/pluk2011-btreeindexesandinnodb

Root Page

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.

Since the root page is allocated when the index is first created, and that page number is stored in the data dictionary, the root page can never relocated or removed. Once the root page fills up, it will need to be split, forming a small tree of a root page plus two leaf pages.

However, the root page itself can’t actually be split, since it cannot be relocated. Instead, a new, empty page is allocated, the records in the root are moved there (the root is “raised” a level), and that new page is split into two. The root page then does not need to be split again until the level immediately below it has enough pages that the root becomes full of child page pointers (called “node pointers”), which in practice often means several hundred to more than a thousand.

Leaf Page Non-Leaf Page

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.

Level

InnoDB assigns each page in the tree a “level”: leaf pages are assigned level 0, and the level increments going up the tree. The root page level is based on the depth of the tree. All pages that are neither leaf pages nor the root page can also be called “internal” pages, if a distinction is important.

示例

image.png

数据词典

FSP_DICT_HDR_PAGE_NO ibdata的第8个page，用来存储数据词典表的信息（只有拿到数据词典表，才能根据其中存储的表信息，进一步找到其对应的表空间，以及表的聚集索引所在的page no）。
Dict_Hdr Page的结构如下表所示：

image.png
数据词典以及加载
https://blog.51cto.com/yanzongshuai/2095128
https://blog.51cto.com/yanzongshuai/2095186

dict_table_t
----dict_index_t
--------unsigned space:32; /*!< space where the index tree is placed /
--------unsigned page:32;/!< index tree root page number */

获取到Root Page，就能遍历整个Index了。
Root Page的格式和普通页格式一样，参见上面示例。

Non-Leaf节点的数据格式：
<Key, Pointer>
以http://zhongmingmao.me/2017/05/12/innodb-btree-index/第一个例子为例