索引，用于提升数据库的查找速度。
索引主要是基于Hash表和B+树。
加速查找速度的数据结构，常见的有两类：
(1)哈希，例如HashMap，查询/插入/修改/删除的平均时间复杂度都是O(1)；
(2)树，例如平衡二叉搜索树，查询/插入/修改/删除的平均时间复杂度都是O(lg(n))；
如果是单行查询确实是哈希索引更快。对于group by 、order by 、比较<>哈希索引时间复杂度会退化成O(n)，而树的有序性，依旧能保持O(logn)的高效率。
一般来说，索引本身也很大，不可能全部存储在内存中，因此索引往往以索引文件的形式存储的磁盘上。 磁盘里的数据加载到内存的时候，是以页为单位加载的，节点与节点之间的数据是不联系的，所以不同的节点，很可能分布在不同磁盘页中，
磁盘的加载次数和树的高度是关联的。越矮加载次数越少。
二叉查找树：最坏的情况，磁盘IO次数等于索引树的高度。为了减少磁盘IO次数，把原本“瘦高”的树变得“矮胖”，这是b-树的特征。
## b树
是一种多路平衡查找树（多叉查找树），它的每一个节点最多包含K个子孩子，K被称为B树的阶，K的大小取决于磁盘页大小。
首先从根节点进行二分查找，如果找到就返回对应节点数据，否则对相应区间的指针指向的节点进行递归进行查找，直到找到节点或者找到null。
M阶的B-树特征：
- 根节点至少有两个子节点。
- 每个中间节点都包含K-1个元素和K个孩子。m/2<=k<=m
- 每个叶子节点都包含K-1个元素。m/2<=k<=m
- 所有叶子节点都位于同一层。
- 每个节点中的元素从大到小排序，节点中K-1个元素正好是K个孩子包含的元素的值域分划。
应用：文件系统，数据库索引（MongoDB）
B+树
是基于B-树的变体，比B-树查询性能更高。
特点：
- 有K个子树的中间节点包含有K个元素（B树是K-1个元素），每个元素不保存数据，只用来索引，所有数据保存在叶子节点。
- 所有叶子节点中包含了全部元素信息，及指向含有这些元素的指针，且叶子节点本身依关键字的大小自小而大顺序链接。
- 所有的中间节点元素都同时存在于子节点，在子节点元素中是最大或者最小元素。
父节点元素都出现在子节点，所有叶子节点包含了全量元素信息。（根节点到某个节点的路径长度一样）
每个子节点都带有指向下一个节点的信息，形成一个有序的链表。（不需要中序遍历）
B+树比B-树更加矮胖，因此查询时的IO次数更少。
B+树查询最终查找到叶子节点，B-树只要找到匹配元素即可。
B-树的查找性能会不稳定（最好时根节点，最差是叶子节点），B+每次查找都是稳定的。
对于范围查找B+优势更加明显。
相比较B-树B+树的优势有三个：
- IO次数更少
- 查询性能更稳定
范围查询简便
InnoDB不支持哈希索引