B树与B+树 hash索引

B树

前面我们看到，虽然平衡二叉树既有链表的快速插入与删除操作的特点，又有数组快速查找的优势，但是这并不是最符合磁盘读写特征的数据结构。

也就是说，我们要找到这样一种数据结构，能够有效的控制树高，那么我们把二叉树变成m叉树，也就是下图的这种数据结构:B树。

B树是一种这样的数据结构：

根结点至少有两个子结点;
每个中间节点都包含k-1个元素和k个子结点，其中 m/2 <= k <= m;
每一个叶子结点都包含k-1个元素，其中 m/2 <= k <= m;
所有的叶子结点都位于同一层;
每个结点中关键字从小到大排列，并且当该结点的孩子是非叶子结点时，该k-1个元素正好是k个子结点包含的元素的值域的分划。

可以看到，B树在保留二叉树预划分范围从而提升查询效率的思想的前提下，做了以下优化：

二叉树变成m叉树，这个m的大小可以根据单个页的大小做对应调整，从而使得一个页可以存储更多的数据，从磁盘中读取一个页可以读到的数据就更多，随机IO次数变少，大大提升效率。

但是我们看到，我们只能通过中序遍历查询全表，当进行范围查询时，可能会需要中序回溯。

不断优化的B树：B+树

基于以上的缺陷，又诞生了一种新的优化B树的树:B+树

B+树在B树的基础上加了以下优化

叶子结点增加了指针进行连接，即叶子结点间形成了链表；
非叶子结点只存关键字key，不再存储数据，只在叶子结点存储数据；

说明：叶子之间用双向链表连接比单向链表连接多出的好处是通过链表中任一结点都可以通过往前或者往后遍历找到链表中指定的其他结点。

这样做的好处是

1.范围查询时可以通过访问叶子节点的链表进行有序遍历，而不再需要中序回溯访问结点。

2.非叶子结点只存储关键字key，一方面这种结构相当于划分出了更多的范围，加快了查询速度，另一方面相当于单个索引值大小变小，同一个页可以存储更多的关键字，读取单个页就可以得到更多的关键字，可检索的范围变大了，相对IO读写次数就降低了。

一些总结

B+ 树和 B 树的区别？

1.B树非叶子结点和叶子结点都存储数据,因此查询数据时，时间复杂度最好为O(1),最坏为O(log n)。

B+树只在叶子结点存储数据，非叶子结点存储关键字，且不同非叶子结点的关键字可能重复，因此查询数据时，时间复杂度固定为O(log n)。

2.B+树叶子结点之间用链表相互连接，因而只需扫描叶子结点的链表就可以完成一次遍历操作，B树只能通过中序遍历。

为什么 B+ 树比 B 树更适合应用于数据库索引？

B+树更加适应磁盘的特性，相比B树减少了I/O读写的次数。由于索引文件很大因此索引文件存储在磁盘上，B+树的非叶子结点只存关键字不存数据，因而单个页可以存储更多的关键字，即一次性读入内存的需要查找的关键字也就越多，磁盘的随机I/O读取次数相对就减少了。
B+树的查询效率相比B树更加稳定，由于数据只存在在叶子结点上，所以查找效率固定为O(log n)。
B+树叶子结点之间用链表有序连接，所以扫描全部数据只需扫描一遍叶子结点，利于扫库和范围查询；B树由于非叶子结点也存数据，所以只能通过中序遍历按序来扫。也就是说，对于范围查询和有序遍历而言，B+树的效率更高。

B+tree索引与hash索引

因为Hash索引底层是哈希表，哈希表是一种以key-value存储数据的结构，所以多个数据在存储关系上是完全没有任何顺序关系的，所以，对于区间查询是无法直接通过索引查询的，就需要全表扫描。所以，哈希索引只适用于等值查询的场景。而B+ 树是一种多路平衡查询树，所以他的节点是天然有序的（左子节点小于父节点、父节点小于右子节点），所以对于范围查询的时候不需要做全表扫描。