mysql innodb B+树高度

1，最小存储单元

1）磁盘扇区：磁盘的最小存储单元，默认512字节。
2）文件系统最小单位块。4k = 8个扇区。尽管一个文件只有1个字节，仍然占用4k空间。

image.png
3）innodb_page_size：InnoDB引擎最小的存储单位，页。4k、8k、16k=4个文件块(默认)
image.png
4）mysql InnoDB .ibd文件(索引和数据文件)的大小始终是16k的倍数。
image.png
5）InnoDB引擎-文件系统-磁盘扇区关系
image.png

2，InnoDB数据组织与查询

1）InnoDB最小存储单位是页。16k，叶子节点和非叶子节点最小单位都是页。B+树中叶子节点存放数据(叶子节点间指针相连，适用于局部性原理)，非叶子节点存放关键字+指针。
2）InnoDB中页指针6B，主键bigint占用8B。

image.png
3）数据查询通过非叶子节点的二分查找，以及数据页指针，找到具体的数据。
4）二级索引检索
image.png
5）B+树的优势(B代表平衡，而非binary)
对比B树：B树叶子和非叶子都存数据，导致非叶子节点指针变少，树的高度增加。I/O操作变多，性能变低。
对比ALV树：树的深度更深，I/O操作多。维护平衡二叉树需要左旋、右旋保持平衡，代价很大。

3，InnoDB树的高度计算

1）假设如下：
数据记录大小1KB -> 叶子节点(页)可以存 16/1 = 16条数据
关键字和指针bigint 8B + 页指针6B -> 非叶子节点可以存 16384/14 = 1170个对象(关键字-页指针)
2）高度为2和3的B+树
高度为2的B+树：1170 * 16 = 18720，约存2w条数据记录。
高度为3的B+树：1170 * 1170 * 16 = 21902400，约存2千万条数据记录。
所以：InnoDB中B+树的高度一般为1~3层。mysql查找一页时代表依次IO，通过主键索引只需要1~3次IO。
3）InnoDB表空间ibd文件中，约定page_no为3的，代表主索引的root page.

image.png
4）root page_no偏移量64位置(在ibd文件中的偏移量为16384 * 3 + 64 = 49216)的前2个字节，存放了B+树的高度。page level
hexdump：查看二进制文件的16进制编码。-n 10输出前10个字节。-s 49216从该位置偏移量开始。
image.png
test_tx的page level 为0：test_tx B+树的高度为1