索引就是一种帮助数据库管理系统高效获取数据的数据。
我们不仅要知道，通常会选择B+ 树作为索引的数据结构，还要知道为什么选它。
这得从索引的存取说起。
索引与数据库的数据一样，都是存放在硬盘上的，相比于内存的存取来说，硬盘的 I/O 存取消耗的时间要高很多。我们通过索引来查找某行数据的时候，需要计算产生的磁盘 I/O 次数，当磁盘 I/O 次数越多，所消耗的时间也就越大。如果我们能让索引的数据结构尽量减少硬盘的 I/O 操作，所消耗的时间也就越小。
我们知道，二分查找法是一种高效的数据检索方式，时间复杂度为 O(log2n)，是不是采用二叉树就适合作为索引的数据结构呢？
首先普通的二叉树在极端情况下会退化为一个链表，效率非常低。
那么平衡二叉树呢，常见的平衡二叉树有很多种，包括了平衡二叉搜索树、红黑树、数堆、伸展树。我们提到平衡二叉树时一般指的就是平衡二叉搜索树。平衡二叉树搜索时间复杂度为 O(log2n)。
数据查询的时间主要依赖于磁盘 I/O 的次数，采用二叉树的形式，即使通过平衡二叉搜索树进行了改进，树的深度也是 O(log2n)，当 n 比较大时，深度也是比较高的，就意味着磁盘 I/O 操作次数多，查询时间特别长。
所以，问题关键还在于降低树深。
B树
如果用二叉树作为索引的实现结构，会让树变得很高，增加硬盘的 I/O 次数，因此很自然想到，一个节点就不能只有 2 个子节点，而应该允许有 M 个子节点 (M>2)。
这就是B 树， Balance Tree，也就是平衡的多路搜索树，它的高度远小于平衡二叉树的高度。在文件系统和数据库系统中的索引结构经常采用 B 树来实现。
B 树作为平衡的多路搜索树，它的每一个节点最多可以包括 M 个子节点，M 称为 B 树的阶。每个磁盘块中包括了关键字和子节点的指针。如果一个磁盘块中包括了 x 个关键字，那么指针数就是 x+1。对于一个 100 阶的 B 树来说，如果有 3 层的话最多可以存储约 100 万的索引数据。对于大量的索引数据来说，采用 B 树的结构是非常适合的，因为树的高度要远小于二叉树的高度。
在 B 树的搜索过程中，其实比较的次数并不少，但如果把数据读取出来然后在内存中进行比较，这个时间就是可以忽略不计的。而读取磁盘块本身需要进行 I/O 操作，消耗的时间比在内存中进行比较所需要的时间要多，是数据查找用时的重要因素，B 树相比于平衡二叉树来说磁盘 I/O 操作要少，在数据查询中比平衡二叉树效率要高。
B+ 树
B+ 树基于 B 树做出了改进，主流的 DBMS 都支持 B+ 树的索引方式，比如 MySQL。B+ 树和 B 树的差异在于以下几点：
1.有 k 个孩子的节点就有 k 个关键字。也就是孩子数量 = 关键字数，而 B 树中，孩子数量 = 关键字数 +1。
2.非叶子节点的关键字也会同时存在在子节点中，并且是在子节点中所有关键字的最大（或最小）。
3.非叶子节点仅用于索引，不保存数据记录，跟记录有关的信息都放在叶子节点中。而 B 树中，非叶子节点既保存索引，也保存数据记录。
4.所有关键字都在叶子节点出现，叶子节点构成一个有序链表，而且叶子节点本身按照关键字的大小从小到大顺序链接。
B+ 树和 B 树的查询过程似乎差不多，但是 B+ 树和 B 树有个根本的差异在于，B+ 树的中间节点并不直接存储数据。这样的好处都有什么呢？
首先，B+ 树查询效率更稳定。因为 B+ 树每次只有访问到叶子节点才能找到对应的数据，而在 B 树中，非叶子节点也会存储数据，这样就会造成查询效率不稳定的情况，有时候访问到了非叶子节点就可以找到关键字，而有时需要访问到叶子节点才能找到关键字。
其次，B+ 树的查询效率更高，这是因为通常 B+ 树比 B 树更矮胖（阶数更大，深度更低），查询所需要的磁盘 I/O 也会更少。并且非叶子节点只存储指针，同样的磁盘页大小，B+ 树可以存储更多的节点关键字。
不仅是对单个关键字的查询上，在范围查询上，B+ 树的效率也比 B 树高。这是因为所有关键字都出现在 B+ 树的叶子节点中，并通过有序链表进行了链接。而在 B 树中则需要通过中序遍历才能完成查询范围的查找，效率要低很多。
总结一下
一，为什么不用平衡二叉树作为索引的数据结构？
1.平衡二叉树必须满足(所有节点的左右子树高度差不超过1)。执行插入还是删除操作，只要不满足上述条件,就要通过旋转来保持平衡，而旋转是非常耗时的,所以AVL树合用于查找多的情况。
2.二叉树的数据结构，会导致“树深”比较深，这种“瘦高”的特性,加大了平均查询的磁盘I0次数，随着数据量的增多，查询效率也会受到影响;
二、B+树和B树在构造和查询性能上有什么差异呢?
B+树的中间节点并不直接存储数据。
1. B+树的查询效率更加稳定:由于非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。
2. B+树的磁盘读写代价更低: B+树的内部节点并没有指向关键字具体信息的指针,因此其内部节点相对B树更小，如果把所有同一内部节点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多，一次性读入内存的需要查找的关键字也就越多，相对IO读写次数就降低了。
3.由于B+树的数据都存储在叶子结点中，分支结点均为索引，方便扫库，只需要扫一遍叶子结点即可，但是B树因为其分支结点同样存储着数据，我们要找到具体的数据，需要进行一次中序遍历按序来扫，所以B+树更加适合在区间查询的情况，所以通常B+树用于数据库索引。
网友评论