B+树

[Bpazy]

原文: https://mqjyl2012.gitbook.io/algorithm/data-structure/balanced-multipath-search-tree#1b-shu-de-ding-yi-1

B+树是B树的一种变形形式。 网上各种资料上B+树的定义各有不同，一种定义方式是关键字个数和孩子节点个数相同。这里我们采取维基百科上所定义的方式，即关键字个数比孩子节点个数小1，这种方式是和B树基本等价的。 除了B树的性质，B+树还包括以下要求：

1. B+树包含2种类型的节点： 内部节点（也称索引节点） 和叶子节点。根节点本身即可以是内部节点，也可以是叶子节点。根节点的关键字个数最少可以只有1个。
2. B+树与B树最大的不同是内部节点不保存数据，只用于索引，所有数据（或者说记录）都保存在叶子节点中。
3. m阶B+树表示了内部节点最多有m-1个关键字（或者说内部节点最多有m个子树），阶数m同时限制了叶子节点最多存储m-1个记录。
4. 内部节点中的key都按照从小到大的顺序排列，对于内部节点中的一个key，左树中的所有key都小于它，右子树中的key都大于等于它。叶子节点中的记录也按照key的大小排列。
5. 每个叶子节点都存有相邻叶子节点的指针，叶子节点本身依关键字的大小自小而大顺序链接。

B+树的搜索、插入、删除操作参考原文。

B+树和B树的区别是：

1. B树的节点(根节点/父节点/中间节点/叶子节点)中没有重复元素，B+树有。
2. B树的中间节点会存储数据指针信息，而B+树只有叶子节点才存储。
3. B+树的每个叶子节点有一个指针指向下一个节点，把所有的叶子节点串在了一起。

B+树的优点在于：

1. 由于B+树在内部节点上不包含数据信息，因此在内存页中能够存放更多的key。 数据存放的更加紧密，具有更好的空间局部性。 因此访问叶子节点上关联的数据也具有更好的缓存命中率。
2. B+树的叶子结点都是相链的，因此对整棵树的便利只需要一次线性遍历叶子结点即可。 而且由于数据顺序排列并且相连，所以便于区间查找和搜索。 而B树则需要进行每一层的递归遍历，相邻的元素可能在内存中不相邻，所以缓存命中性没有B+树好。

但是B树也有优点，其优点在于： 由于B树的每一个节点都包含key和value，因此经常访问的元素可能离根节点更近，因此访问也更迅速。

[Bpazy]

在MySQL Innodb存储引擎中的B+树的一个节点大小为“1页”，也就是16k。也即代表B+树的每个节点可以存16KB数据。

非叶子结点：

• 假设主键类型为bigint，占用8Byte，指针可以设置为占用6Byte，总共14Byte。这样就可以算出一个非叶子节点大概可以存放16KByte/14Byte=1170个“主键+指针”的组合。即一个非叶子结点可以指向 1170 个页。
• 假设主键类型为int，占用4Byte，指针可以设置为占用6Byte，总共10Byte。这样就可以算出一个非叶子节点大概可以存放16KByte/10Byte≈1600个“主键+指针”的组合。即一个非叶子结点可以指向 1600 个页。

叶子结点：

• 在B+树中，真正的数据是只存储在叶子节点中的。这里我们假设我们的一行数据大小是1K，那么我们一个叶子节点就可以存16KByte/10Byte=16条（行）数据。

关于各种类型占据的空间大小，参考这里: https://github.com/Bpazy/blog/issues/292

由此，可以推算出公式：

两层总数 = 非叶子节点(根) 叶子节点。 三层总数 = 非叶子节点(根) 非叶子节点 * 叶子节点。

主键为bigint（约2000w）： 2层B+树的话：可以存放1170个16条=18720条（行）数据。 3层B+树的话：可以存放1170个1170个*16条=21902400条（行）数据。

主键为int（约4000w）： 2层B+树的话：可以存放1600个16条=25600条（行）数据。 3层B+树的话：可以存放1600个1600个*16条=40960000条（行）数据。 所以三层B+树也就差不多2000w条或4000w条数据。

[Bpazy]

2000W 行分表问题

2100w 行以后，真的会发生性能极速劣化吗？并不会!

其实，每一次 B+ 树增高，都只会增加两个索引页，修改一个索引页，加起来只修改了三个 16KB 的数据页，无论是磁盘 IO 还是 Buffer Pool 缓存失效，对性能的影响都微乎其微：

索引从三层转换到四层，只增加了一次 IO，绝对性能降低幅度的理论极限只有1/3，而且在有 Buffer Pool 存在的情况下，性能差异微乎其微，只增加了1~2次比大小的计算成本。

那是否意味着不需要再分表了呢？

虽然三层索引和四层索引看起来性能差异不大，但是如果你的单行数据比较大，例如达到了 5KB，还是建议做一下横向分表的，这才是效果最立竿见影的减少磁盘 IO 次数的优化方法：

• 单行数据为 0.9KB 时，三层树的极限行数是 2100 万，但是如果单行数据来到 5KB，那这个极限会变成 285 万行，这可能就不太够了
• 数据页拥有局部性：每次从磁盘读取都是一整页的数据，所以读取某一行数据以后，它 id 附近的数据行也已经在内存缓存里了，读取性能十分优异
• 在连续读取多行时（例如全表条件查询），巨大的单行数据将在让“局部性”优势迅速丧失的同时，会引发磁盘 IO 次数出现数量级规模的上升，这就是单行数据比较大的表读取起来感觉格外慢的原因

到底该何时分表？

2017 年发布的阿里巴巴 Java 开发手册中写道“单表行数超过 500 万行或者单表容量超过 2 GB ，才推荐进行分库分表”，被很多技术博文写成了：阿里巴巴推荐超过 500 万行的表进行分表，这种理解是错误的。

虽然经过我的实测，在每行数据定长 1024 字节，Buffer Pool 配置为 22GB，在单表体积 24GB 的情况下，四层索引和三层索引并没有任何性能差异，但是现实世界中的数据表可不是这么严丝合缝：

1. 为了节约空间和保持扩展性，绝大多数短字符串类型采用的是 varchar 而非定长的 char，这就让 level=0 的每一页包含的数据行数不一致，这会让这颗“平衡多路查找树”不怎么平衡
2. 生产表经常面临数据删除和更新：同层的页之间的双向链表和不同层页之间的单向指针都需要经常变化，同样会让这棵树变的不平衡
3. 一张表使用的越久，ibd 文件中的碎片就越多，极端情况下（例如新增 10 行删除 9 行）会让数据页的缓存几乎失效
4. 磁盘上单文件体积过大，不仅在读取 IOPS 上不如多文件，还会引发文件系统的高负载：单个文件描述符也是一种单点，大文件的读写性能都不太行，还容易浪费大量内存

那么，该如何回答“到底该何时分表”这个问题呢？很遗憾并没有一个放之四海皆准的答案，这和每个表的读取、新增、更新的具体情况是分不开的。

虽然在数据库技术层面我们无法给出何时分表的答案，但是从软件工程层面我们可以得出一个结论：

能不分就不分，不到万不得已不搞分表，如果能靠加索引或者加内存来解决就不要考虑分表，分表会对业务代码造成根本性的影响，会产生长久的技术债务。

Refer: https://lvwenhan.com/tech-epic/506.html