B+树详解：数据库索引背后的高效数据结构
B+树详解：数据库索引背后的高效数据结构
B+树是一种在数据库和文件系统中广泛使用的自平衡树形数据结构。它在B树的基础上进行了优化，通过在相邻的叶子节点间添加双向链表，不仅提供了高效的范围查询能力，还降低了树的层级，提高了查询效率。本文将详细介绍B+树的原理及其在数据库中的应用。
什么是B树
B树（B-Tree）是一种自平衡的树形数据结构，主要用于数据库和文件系统中存储大量数据。与二叉树不同，B树允许每个节点有多个子节点，并且每个节点可以存储多个键值。
什么是B+树
B+树就是在B树的基础上为相邻的叶子结点新增了双向链表。注意：没有B-树，网上一切关于B-树的言论纯属错误，相当于将π抄成了√2。
索引为什么要使用B+树
在此之前先科普下：
- 在内存中查询和在磁盘查询性能不是一个数量级
- 每次查询都是一次磁盘IO，树的层级越多查询次数越多，即层级越多查询越慢
- 下面提到的二叉树特指查询二叉树
- 非叶子结点称为树节点
Hash索引
Hash索引和树那个快？答案是Hash索引，有了Hash索引为什么还要用树呢？直接说了Hash索引不支持范围查询，即我们平常使用的
select * from tb where id>1
Hash索引不支持。所以直接Pass，反过来如果你的业务上不需要范围查询，你在建索引的时候就选择Hash数据结构效率就更高，需要灵活应用。
二叉树
二叉树怎么了？我们先回顾下二叉树是怎么插入的，每进来一个新的值就和左右子树进行比较小的放左边大的放右边。如果按顺序进来二叉树就会一直插在右边，就形成了一个链表。查询效率会达到最低，所以也被Pass。更何况二叉树天生比多叉树层级要多。
B树
B树是一个多叉树，规避了二叉树存在的哪些弊端。首先它的每个节点都是数据节点（以下统称为行数据），就不支持范围查询了，也可以强行进行范围查询，但涉及到回溯，查询效率就不好预估了。其次这种保存方式生成的树，层级不是最优。
B+树
在B树的基础上进行改造，将行数据统一放到叶子结点上，在将相邻的叶子节点间建立双向链接，范围查询时先根据树结构查询起点，在根据链表进行范围查询，这样就提供了范围查询的能力。构建链表所占用的空间几乎可以忽略，一般是2*6b。
将行数据迁移到叶子结点后，中间的树节点也可以充分利用起来，原本存放完整行数的节点我们只保存其Key（key指的是索引字段），这样一个节点就能保存多个key，相较于B树的一个节点只能保存一条行数据（对应一个key），相同层级的树能保存的数据就能更多。换句话说就是相同的数据量B+树的层级更低。结合前面提到的层级越低性能越高，其查询效率就远超B树。
然后我们将树节点的查询设置为16kb，刚和和Innodb访问磁盘空间最小单位保持一致，每次查询就是对应一次磁盘IO，大小一致，处理器会进一步的帮我们优化访问。
最后也是因为其数据都在叶子结点上，所以其查询效率就会显得很稳定，不会有的快有的慢。
B+树的插入过程
页分裂
索引是存在页里面的，如果是按顺序插入，当页满了之后就是向磁盘申请开第二个空间，把新值直接继续存储在新开的空间。涉及到的分裂过程就不是很复杂。
如果是乱序插入的。现在有两页了，要插入的行刚好位于中间，首先要在开一页。第三页有了之后，就不是直接存在新开的空间了。他会找到他应该待的那一页，找到50%的部分把他们移到第三页，然后把自己加到第三页。然后调整三页之间的链表指针。
页合并
当删除之后，页的可用空间会慢慢达到阈值（默认页合并阈值就是50%），达到阈值后就会找到相邻的两页看看有没有合并的可能性，如果可以就合并达到优化磁盘空间的目的。值得注意的是现在大部分业务采用的是伪删除，涉及到页合并就比较少了
优化
有了这个插入过程我们可以想到怎么样使我们的查询更快？对就是定期索引碎片整理，整理的过程会将页进行最大限度的合并，从而减少页的数量，降低树的层级。注意要选择访问量小的时候，因为这个操作是会影响查询的。
数据结构的魅力
键值和指针的关系
假设一个非叶子节点有 n个键值，则它会有 n+1个指针。这种关系可以通过以下逻辑理解：
- 每个键值将数据划分为一个范围。
- 假设一个非叶子节点有 3 个键值 K1,K2,K3那么这些键值可以将数据划分为 4 个范围：
- 小于 K1 的数据。
- 大于等于 K1 且小于 K2 的数据。
- 大于等于 K2且小于 K3的数据。
- 大于等于 K3 的数据。
指针对应范围
- 每个范围需要一个指针指向对应的子树。
- 因此，对于 n个键值，需要 n+1个指针来分别指向这 n+1个范围的子树。
计算
假设一行数据的大小为1k，一页的大小为16k，一个叶子结点就能存放16行数据（对应表里的16条数据）。
假设key是int类型就是4，指针一般是6，那么就得出4n+6n+6=16*1024。n=1637。指针多一个就是1638.
如果高度为2：共计1638*16=26000条数据
如果高度为3：1638163816=4200万，一般一行数据也不会有1k这么大，能存储的数据就更多了。
千万级的数据，只需要三次查询就拿到了，访问磁盘48kb的数据有多快不用多说了吧。
注意：树节点中的key之间用的是二分法查找，在内存中进行的，查询时间可忽略不计。