漫画：什么是B+树，B+树层数计算（面试官直呼内行）

1.什么是B+树

一个m阶的B树具有如下几个特征：

1.根结点至少有两个子女。

2.每个中间节点都包含k-1个元素和k个孩子，其中 m/2 <= k <= m

3.每一个叶子节点都包含k-1个元素，其中 m/2 <= k <= m

4.所有的叶子结点都位于同一层。

5.每个节点中的元素从小到大排列，节点当中k-1个元素正好是k个孩子包含的元素的值域分划。

一个m阶的B+树具有如下几个特征：

1.有k个子树的中间节点包含有k个元素（B树中是k-1个元素），每个元素不保存数据，只用来索引，所有数据都保存在叶子节点。

2.所有的叶子结点中包含了全部元素的信息，及指向含这些元素记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。

3.所有的中间节点元素都同时存在于子节点，在子节点元素中是最大（或最小）元素。

B-树中的卫星数据（Satellite Information）：


B+树中的卫星数据（Satellite Information）：

需要补充的是，在数据库的聚集索引（Clustered Index）中，叶子节点直接包含卫星数据。在非聚集索引（NonClustered Index）中，叶子节点带有指向卫星数据的指针。

第一次磁盘IO：

第二次磁盘IO：

第三次磁盘IO：






B-树的范围查找过程

自顶向下，查找到范围的下限（3）：

中序遍历到元素6：

中序遍历到元素8：

中序遍历到元素9：

中序遍历到元素11，遍历结束：

B+树的范围查找过程
自顶向下，查找到范围的下限（3）：

通过链表指针，遍历到元素6, 8：

通过链表指针，遍历到元素9, 11，遍历结束：

• B+树的特征：
  1.有k个子树的中间节点包含有k个元素（B树中是k-1个元素），每个元素不保存数据，只用来索引，所有数据都保存在叶子节点。
  2.所有的叶子结点中包含了全部元素的信息，及指向含这些元素记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。
  3.所有的中间节点元素都同时存在于子节点，在子节点元素中是最大（或最小）元素。

• B+树的优势：
  1.单一节点存储更多的元素，使得查询的IO次数更少。
  2.所有查询都要查找到叶子节点，查询性能稳定。
  3.所有叶子节点形成有序链表，便于范围查询。

• 其他说明：
  （1）卫星数据是什么？
  卫星数据是b树的，索引树节点所对应的那一行数据
  （2）要么跟节点的最大元素是整个树的最大值，要么跟节点的最小元素是整个树的最小值
  （3）既然B+树中间节点和根节点不包含数据，那根节点和中间节点的搜索可不可以一次io加载到内存？叶子节点磁盘io一次。
  在节点占用空间恒定的情况下，B+树单个节点的元素更多，比如同样节点大小，B树的每个节点有100个元素，B+树的每个节点就可以装下1000个元素，这样的好处是：树的高度降低了。一次IO读出跟和所有中间节点，属于一种极端情况，在树的规模不大的时候或许可以做到。
  （4）为什么只有B+树的卫星数据在叶子节点上？
  因为B+树的非叶子节点是没有卫星数据的，非叶子节点只起到索引的作用。
  （5）hashmap为什么不把红黑树改成B树？
  因为二叉查找树的查找效率是最高的，如果内存能装下完整的树，最好使用二叉查找树，B树是退而求其次的方式
  （6）B+树是以空间换时间，父节点元素在子节点重复出现，增加了少量空间，换来的是范围查询的便利。
  （7）所有的中间节点元素都同事存在于子节点，在子节点中是最大或最小元素，这是一开始就规定好的。
  （8）为什么要强调B+树查询性能稳定呢？场合是啥？
  B+树的查询每次都查到叶子节点，所以IO次数稳定，是向一个数据库的查询，有时候执行10ms，有时候执行100ms，肯定是不合适的，还不如每次都执行30ms。

2.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

• 参考：b+树图文详解，漫画：B+树，B+树层数计算（面试官直呼内行），公众号：程序员小灰