B+树层数计算（面试官直呼内行）

B+树结构简述

跟其它tree结构一样，根节点只有一个，根节点可以为叶子节点或者非叶子节点，B+树的非叶子节点(包括根节点)可以有多个子节点，它的非叶子节点仅保存索引列和指针，不保存具体行记录；

啥是根节点

最上面那个就叫根节点

啥是非叶子节点

不是叶子节点的节点都叫非叶子节点

啥是叶子节点

最下面那些最终节点就叫叶子节点

如何计算层数

首先搞清楚一个常识，我们都知道计算机在存储数据的时候，有最小存储单元，这就好比我们今天进行现金的流通最小单位是一毛

在计算机中磁盘存储数据最小单元是扇区，一个扇区的大小是 512 字节，而文件系统（例如XFS/EXT4）他的最小单元是块，一个块的大小是 4k

而对于我们的 InnoDB 存储引擎也有自己的最小储存单元——页（Page），一个页的默认大小是 16K，page可以储存指针，也可以储存行记录，其中指针指向下一个page的地址

好，知道这个，计算层数就简单了，我们先假设有两层，第一层为非叶子节点，保存指针，第二层为叶子节点，保存具体行记录

那么两层高度的b+树能存储的数量 = 根节点指针数*每个指针对应第二层的行记录数

ok建议你先捋捋，不着急

根节点指针数

怕你没认真看上面，我再说一遍，B+树的非叶子节点仅保存索引字段和指针，假设主键为bigint类型，InnoDB 的bigint占用8个字节，指针占用6个字节，8+6=14，所以我们可以得出，一个page能存放的指针个数为16k/(8+6)约等于1170

每个指针对应第二层的行记录数

再来说说一个page能存储多少条行记录，常规的互联网项目单条行记录大小约为1k，那么一个page能存储的行记录数为16k/1k=16

所以一个2层高的b+树能存储的行记录数大约为1170*16=18720

3层为1170*1170*16约等于2190w

ok我话说完

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。