A variety of tree structures
Search binary tree, B tree, B+ tree, B* tree
2. Tree splitting
Mysql storage engine and index
4. Page structure
Now look at how to locate a Record:
1 starts traversing an indexed B+ tree through the root node, and finally reaches a Page that stores all the leaf nodes through the layers of non-leaf nodes.
2 Traverses the single-linked list starting at the “Infimum” node within the Page (this traversal is often optimized) and returns successfully if the key is found. If the record reaches “supremum”, there is no appropriate key in the current Page. In this case, use the Next Page pointer of the Page to go to the Next Page and continue the search from “Infimum”.
Page and B+ tree nodes
Combining the STRUCTURE of the B+ tree with the contents of the four records described above, we can finally draw a panoramic picture. Since the B+ tree of the secondary index has a similar structure to the primary key index, only the structure diagram of the primary key index tree is drawn here, including only “primary key non-leaf node” and “primary key leaf node”, which are the green and yellow parts in the figure above.
This is part of a B+ tree. Note that there is no one-to-one relationship between Page and B+ tree nodes. Page only serves as a storage container for Record, and its purpose is to facilitate batch management of disk space. Page 47 in the figure above is split into two independent nodes in the tree structure. A page can be split into multiple nodes, and a node can correspond to multiple pages.
Reference:
Mysql index structure diagram to www.jianshu.com/p/a1420a2f5…
Graphic MySQL index: b-tree, B + tree | algorithm will see a series of 30 developer.aliyun.com/article/759…
Mysql the underlying parsing – innodb file system basic structure, variety, (page), including connection, parsing, cache, engine, storage and other cloud.tencent.com/developer/a…
How many rows can InnoDB store in a B+ tree? Mp.weixin.qq.com/s/xUJp62fFX…
[11] of embracing MySQL MySQL InnoDB zhuanlan.zhihu.com/p/71204073 file storage structure