Mysql索引数据结构
Hash表与B+树
树的查询效率高O(log N)，可以保持基本有序。
B-树（B树）实现细节
磁盘IO消耗时间比较长，数据库索引存储在磁盘上，数据量极大的时候，索引所占的存储空间也是非常可观的。
索引查询时，将不可能将所有的索引全部加载到内存中，只有逐一加载每一个索引页（即对应B树中的节点）。
索引查找时，最坏条件下的IO次数即为索引树的高度。
为了减少磁盘IO的次数，需要把高瘦的树结构变得矮胖。这就是B-树的特征之一。
B树是一种多路平衡查找树，他的每一个节点最多包含K个孩子，K即位B树的阶。K的大小取决于磁盘页的大小。
B-树的特征：(m阶)
1. 根节点至少有两个子女。
2. 每个中间节点都包含k-1个元素和k个孩子。其中m/2 <= k <= m
3. 每一个叶子节点都包含k-1个元素，其中m/2 <= k <= m
4. 所有的叶子节点都位于同一层。
5. 每个节点中的元素从小到大排列，节点当中k-1个元素正好是k个孩子包含的元素的值域分划
B+树
B+树是B树的一种变体，有着比B树更高的查询性能。
M阶的B树有以下特征:
[if !supportLists]1. [endif]有K个子树的中间节点含有K个元素（B树中是K-1个），每个元素不包含数据，只用来索引，所有的数据都包含在叶子节点中。
[if !supportLists]2. [endif]所有的叶子节点包含了全部元素的信息，及指向包含这些元素记录的指针。且叶子节点本身依照关键字的大小自小而大，顺序排列。
[if !supportLists]3. [endif]所有的中间节点元素都同时存在与子节点，在子节点中是最大（或最小的元素）。
根节点中的最大元素，代表整个树中的最大元素。
卫星数据：索引元素所指向的数据记录。在数据库中的某一行，在B树中，无论是中间节点还是叶子节点，都带有卫星数据。
需要补充的是，在数据库的聚集索引（Clustered
Index）中，叶子节点直接包含卫星数据。在非聚集索引（NonClustered Index）中，叶子节点带有指向卫星数据的指针。
在B+树中，中间节点不含有卫星数据，同样大小的磁盘页，可以包含更多的节点指针。IO次数更少。
B+树的查询必须查到叶子节点，而B-树只需要查到所查元素即可。
B-树的查找性能不稳定，B+树的每一次查找性能都是稳定的。
B-树的范围查找采用中序遍历，性能不好。B+树先找到边界，然后进行链表操作，性能高。
B-树与B+树的插入删除操作大体一致。
B+树的特征：
1.有k个子树的中间节点包含有k个元素（B树中是k-1个元素），每个元素不保存数据，只用来索引，所有数据都保存在叶子节点。
2.所有的叶子结点中包含了全部元素的信息，及指向含这些元素记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。
3.所有的中间节点元素都同时存在于子节点，在子节点元素中是最大（或最小）元素。
B+树的优势：
1.单一节点存储更多的元素，使得查询的IO次数更少。
2.所有查询都要查找到叶子节点，查询性能稳定。
3.所有叶子节点形成有序链表，便于范围查询。
