引言
之所以写这篇文章，是因为数据库的索引里涉及到了B+树，而面试中有可能会问到为什么采用B+树而不采用B树
该文章以以下脉络进行：
首先从索引的功能进行剖析，理解索引要达到的目的是什么，从而明白我们要以什么为目的选取存储索引的数据结构，从而解决为什么索引用的数据结构是B+树而不是B树
数据结构教程-李春葆（书）
索引、它的作用以及适用范围
索引是对数据库表中一个或多个列的值进行排序的数据结构，以协助快速查询、更新数据库表中数据
具体的来说，它的作用为：
- 大大加快数据的检索速度，这也是创建索引的最主要的原因；
- 加速表和表之间的连接；
- 在使用分组(group by)和排序子句(order by)进行数据检索时，同样可以显著减少查询中分组和排序的时间；
- 通过创建唯一性索引(distinct)，可以保证数据库表中每一行数据的唯一性；
从上述优点，我们可以总结出，这些字段是适合创建索引的
- 经常用作查询的字段
- 经常用作表连接的字段
- 经常出现在order by, group by, distinct 后面的字段
为什么要用树存储索引
根据上述要求，我们可以联想到算法题中常见的题目：如何在无序数组中查找某个元素，在我所学的《数据结构教程》这本教材中提到，查找的方法有这些，查找方法与数据结构息息相关：
线性表适合于静态查询
线性表作为组织形式的时候，以折半查找的效率最高，但是由于折半查找要求表中的元素关键字有序，且不适合采用链表存储结构，因此当表的插入或删除操作频繁时，为了维护表单额有序性，需要移动表中的很多元素，而这种移动的开销会抵消折半查找的优点
树表适合动态查询
哈希表适合于数组的关键字与存储地址存在某种映射关系的情况
很明显，一通分析过后，数据库系统比较适合于用树表存储索引，然而，无论二叉搜索树还是平衡二叉树，当数据量比较大时，都会由于树的深度过大而造成I/O读写过于频繁，进而导致查询效率低下，因此对于索引而言，多叉树结构成为不二选择。特别地，B-Tree（平衡多路查找树）的各种操作能使B树保持较低的高度，从而保证高效的查找效率。
那么B树和B+树有什么区别呢，为什么我们要采用B+树呢？
为什么要用B+树
实际上，B+树就是为了满足索引文件结构而诞生的，B+树和B树的区别如下：
B树
每个节点都存储key和data，所有节点组成这棵树，并且叶子节点指针为null。
B+树
只有叶子节点存储data，叶子节点包含了这棵树的所有键值，叶子节点不存储指针。
可以看到，他们的主要区别在于非叶子节点是否存储key对应的data值，对应的，data在数据库系统里就是元组所在的物理地址（指针）
实际应用到数据库系统里时，两者的区别在于：
- B+tree的磁盘读写代价更低：B+tree的内部结点并没有指向关键字具体信息的指针(data部分)，因此其内部结点相对B 树更小。如果把所有同一内部结点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多，相对来说IO读写次数也就降低了；
- B+tree的查询效率更加稳定：由于内部结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引，所以，任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当；
- 最主要的原因：B+树只要遍历叶子节点就可以实现整棵树的遍历，而且在数据库中基于范围的查询是非常频繁的，而B树只能中序遍历所有节点，效率太低。
京公网安备 11010502036488号