聊一下索引的底层数据结构，着重介绍现在用的比较广泛的B树与B+树。

hash 表

hash表的数据结构在此就不多赘述了，直接说hash表的缺点：

  • 需要大量内存空间，因为每次使用hash表的时候都需要将全量的数据加载到内存中。（memory存储引擎使用hash索引）
  • 使用hash表时需要设计优秀的hash算法，否则会导致数据分布不均匀，浪费存储空间，查询效率低下。
  • hash表只能支持等值搜索，不能范围或区间搜索。比如要查询id < 500的人，hash表只能从1到499依次查出来。这是hash表比较致命的缺点。

二叉树

使用二叉搜索树可以使用二分查找方式查找数据，但是如果插入的数据是递增的，二叉树就会退化成链表，树的深度也很大，而树的深度与查找次数成正比（下面会解释，减少树的深度正是提高索引效率的核心思路之一）。因此单纯的二叉搜索树效率可能会低下。

那么使用二叉平衡树（AVL树）呢？
二叉平衡树要求左右子树高度差不大于1，这避免了上面数据退化成链表的情况，提高了搜索效率，但是在插入数据时，二叉平衡树为了保证平衡性，插入时要进行旋转，而这降低了插入效率。此外，在数据量大的情况下，二叉平衡树还是无法避免深度大的情况。

红黑树

为了解决二叉树插入效率低的情况，在看看红黑树，他也是二叉平衡树，但它只要求最长子树的深度不超过最短子树的二倍，而且还添加了变色的行为来保证树的平衡性。

可是这还是无法避免深度大的情况，接下来的思路大家应该也想到了，就是增加树的的分支来减少树的深度，这就是B树。

B树

B树最大的特点是每个节点可以包含多个Key值，B树中有一个叫degree概念，表示每个节点最多可以存储N-1个节点。

B树特点：

  1. 所有键值分布在整颗树中
  2. 搜索有可能在非叶子结点结束，在关键字全集内做一次查找,性能逼近二分查找
  3. 每个节点最多拥有m个子树
  4. 根节点至少有2个子树
  5. 分支节点至少拥有m/2颗子树（除根节点和叶子节点外都是分支节点）
  6. 所有叶子节点都在同一层、每个节点最多可以有m-1个key，并且以升序排列

下面看一个实例：

Bshu

实例图说明：

每个节点占用一个磁盘块，一个节点上有两个升序排序的关键字和三个指向子树根节点的指针，指针存储的是子节点所在磁盘块的地址。两个关键词划分成的三个范围域对应三个指针指向的子树的数据的范围域。以根节点为例，关键字为 16 和 34，P1 指针指向的子树的数据范围为小于 16，P2 指针指向的子树的数据范围为 16~34，P3 指针指向的子树的数据范围为大于 34。

查找关键字过程：

  1. 根据根节点找到磁盘块 1，读入内存。【磁盘 I/O 操作第 1 次】

  2. 比较关键字 28 在区间（16,34），找到磁盘块 1 的指针 P2。

  3. 根据 P2 指针找到磁盘块 3，读入内存。【磁盘 I/O 操作第 2 次】

  4. 比较关键字 28 在区间（25,31），找到磁盘块 3 的指针 P2。

  5. 根据 P2 指针找到磁盘块 8，读入内存。【磁盘 I/O 操作第 3 次】

  6. 在磁盘块 8 中的关键字列表中找到关键字 28。

但是B树依旧有缺点：

  1. 每个节点都有key，同时也包含data，而每个页存储空间是有限的，如果data比较大的话会导致每个节点存储的key数量变小

  2. 当存储的数据量很大的时候会导致深度较大，增大查询时磁盘io次数，进而影响查询性能

B+树

B+ Tree 是基于B Tree 和叶子节点顺序访问进行实现，它具有 B Tree 的平衡性，并且通过顺序访问指针来提高区间查询的性能。此外，B+ 树不在非叶子节点存储数据，只存储Key值，使得B+ Tree每个节点可以包含更多的节点。

B+Tree是在B Tree的基础之上做的一种优化，变化如下：

  1. 非叶子节点存储key，叶子节点存储key和数据
  2. B+ Tree每个节点可以包含更多的节点，这个做的原因有两个，第一个原因是为了降低树的高度，第二个原因是将数据范围变为多个区间，区间越多，数据检索越快
  3. 叶子节点两两指针相互连接（符合磁盘的预读特性），顺序查询性能更高

如图：
B+shu

注意：在B+Tree上有两个头指针，一个指向根节点，另一个指向关键字最小的叶子节点，而且所有叶子节点（即数据节点）之间是一种链式环结构。因此B+Tree 支持两种查找运算：一种是对于主键的范围查找和分页查找（解决Hash表缺点），另一种是从根节点开始，进行随机查找。

查找过程

借助索引查找时，现在B+树根节点进行二分查找，找到所查找项对应区间的结点之后继续递归的查找，直到在叶子节点找出Key所对应的data。
插入删除操作会破坏平衡树的平衡性，因此在进行插入删除操作之后，需要对树进行分裂、合并、旋转等操作来维护平衡性。这也是索引共同的缺点。

优点

  1. B+树能显著减少IO次数，提高效率
  2. B+树的查询效率更加稳定，因为数据放在叶子节点
  3. B+树能提高范围查询的效率，因为叶子节点指向下一个叶子节点
  4. B+树采取顺序读

看了下面的解释，我们会更深入的了解B+ 树高效的原因

为什么B+ 树有更高的性能？

我们先看一下数据库数据从查找到传递在磁盘上经历哪些步骤：

操作系统一般将内存和磁盘分割成固定大小的块，每一块称为一页（数据页16KB，6384字节），内存与磁盘以页为单位交换数据。数据库系统将索引的一个节点的大小设置为页的大小，使得一次 I/O 就能完全载入一个节点。

cipan
如图，磁盘结构包括：盘片，磁头，主轴，集成电路板。

磁盘上有一条条磁道，数据存于磁盘的磁道上，要查找并读取一个存储的数据，磁头从不存储数据的着陆区移动到磁道上，经过磁盘旋转找到对应数据，在将数据传送的内存。

那么我们就可以发现：

单次的IO时间 = 寻道时间 + 旋转延迟 + 传送时间

此时我们再来看B+ 树的数据结构为什么能更高效：

  1. B+ 树有更低的树高

平衡树的树高 O(h)=O(logdN)，其中 d 为每个节点的出度。 因为B+ Tree 的非叶子节点不存放数据，只存储Key，B+ Tree 的出度一般都非常大（红黑树的出度为 2），所以 B+ Tree 的树高比较低，而从B+ 树一层层查找的过程我们可以推理出，每一层（每次查询）都要在磁盘进行搜索（寻道），更低的树高可以有效的减少寻道时间。

  1. 磁盘预读特性

为了减少磁盘 I/O 操作，磁盘往往不是严格按需读取，而是每次都会预读。预读过程中，磁盘进行顺序读取，顺序读取不需要进行磁盘寻道，并且只需要很短的磁盘旋转时间，速度会非常快。并且可以利用预读特性，相邻的节点也能够被预先载入。B+ 树叶子节点相连的特性恰恰迎合了磁盘的顺序读，减少了旋转延迟。

总结：B+ 树除了数据结构本身的高效，还迎合了磁盘的I/O机制，所以能更高效。