MySQL连载：一颗索引树有多高

文字：1009 阅读：3分钟

说了数据库为什么使用B+树作为索引，面试时还经常会考：

“一个B+树索引的高度”

“一个B+树索引可以存放多少行数据”

这个问题其实隐含着：B+树结构，索引树高度和页面I/O的关系，索引高度的理论计算方法，如何查看索引树真实高度等几个相关问题。

页

我们知道在B+树的非叶节点和叶节点上都是用页的方式存储数据，页是InnoDB存储引擎中最小的存储单元，一页的大小默认是16K。

mysql > show variables like 'innodb_page_size'

可以通过这个命令来查看，当然这个大小也是可以通过参数配置。

在叶子节点上页可以用来存放记录数据，而非叶子节点上用来存放键值和指针。

我们通过索引组织在查找数据时，指针指在哪个页上，就要进行I/O加载数据。

所以，我们可以得出第一个结论：

B+树索引结构作为一个平衡树，每个叶子节点到根节点的高度都是一样的，索引树越高，I/O的请求次数越多，而我们使用索引的目标就是降低I/O请求次数

叶子节点存储数据记录，我们假设一行数据的大小是1K左右，那16K就可以存16条数据。

非叶子节点存储指针和主键，主键ID设置bigint类型，长度为8字节，而指针在InnoDb源码中设置为6字节，一共14个字节，那一个页中就能存储 16*1024/14 = 1170.

那么如果B+索引树的高度为2，那能存放的记录为1170*16 = 19720条。

那么如果树的高度为3，那存放的记录为1170*1170*16 = 21902400，虽然这只是估算，但3层高度就可以达到2千万级的数据存储，在一些大厂里要求数据超过2千万即要分库分表，也是为了保证索引效率。

树有多高

在MySQL information_schema数据库INNODB_SYS_INDEXES表中，存储所有索引记录。

SELECT b.name,
       a.name,
       index_id,
       TYPE,
       a.space,
       a.PAGE_NO
FROM information_schema.INNODB_SYS_INDEXES a,
     information_schema.INNODB_SYS_TABLES b
WHERE a.table_id = b.table_id
  AND a.space <> 0;

TYPE 代表索引类型 3代表聚集索引  0代表非唯一二级索引

SPACE代表每个表的空间ID号

PAGE_NO代表根页的序列号

hexdump -s 49216 -n 10 ./user.ibd
000c040 0200 0000 0000 0000 1600
000c04a

我们使用hexdump 命令可以查看到根页的page_level,

树的高度 = page_level + 1 ，page_level为0200代表树的高度为3。

49216是怎么计算公出来呢，公式为：

page_no*innodb_page_size+64, 64为偏移量。

=16384*3+64=49216

好了，今天我们又解决了一个面试题。既然我们已经搞定了索引原理，明天我们继续说说如何正确的使用索引。

PS:

我们都爱做能力范围之内的，因为可控，自己可以预估出时间和预判出相关人的反应，可往往这些事情不能让你的能力更进一步，同时可怕的是在领导的眼里，你正在被这些事情束缚。

多做些需要自己抬抬脚跟才能完成的事情，无疑处理的过程中，你需要协调更多的人，搞定更多失控边缘的问题，但过后，事情也不过just so so 。

关注我，带你一起进化！

更多面试资料