MySQL 索引——数据结构实现

通过使用二叉查找树的结构，我们可以提升数据的查找效率，它的时间复杂度是 O(logn)，但是当存储的数据是具有前后顺序性的时候，此时的查找效率就会变为O(n)，当然，我们可以通过平衡二叉查找树解决这个问题，但是呢，对于大规模数据存储实现索引查询的背景下，二叉树查找树会因为数据量的剧增而导致树高将会非常高，进而导致导致大量的I/O产生，众所周知，I/O的性能通常是整个系统的瓶颈，因此降低系统 I/O 次数能显著提升系统性能。
所以我们只能在降低系统 I/O 次数方面下手，因此增加树的“叉”树就可以解决 I/O 的问题；根据平衡二叉查找树的特点，因此 平衡 多路查找树 就应用而生了，也就是我们通常所说的 B 树数据结构

B 树的定义

一棵m阶的B树满足下列条件：（如果每个节点最多有m个孩子，这样的树就是m阶B树。）

1. 树中的每个节点最多有m个孩子。（m >= 2）
2. 除根节点和叶子节点外，其他每个节点至少包含ceil(m/2)个节点。
3. 根节点至少包含两个孩子（B树只有一个节点除外）
4. 所有叶节点在同一层，B树的叶节点可以看成一种外部节点，不包含任何信息。
5. 有K个关键字（关键字按递增次序排列）的非叶子节点恰好有k+1个孩子
   而 B+ 树更适合存储索引

B+ 树

1. B+树更适合用来做存储索引。
2. B+树的磁盘读写代价更低。（B+树的内部结构并没有指向关键字具体信息的指针，也就是不存放我们的数据，只存放索引信息，因此其内部节点相对于B树更小，如果把所有同一内部节点的关键字存放在同一盘块中，这个盘块所能容纳的关键字也越多，一次性需要读入内存中查找的盘块也就越多，相对来说，I/O读写次数降低了）
3. B+树的查询效率更加稳定（由于内部节点并不是指向最终内容的节点，而只是叶子节点关键字的索引，所以任何关键字的查找必须走一条从根节点到叶子节点的路，所有关键字的查询的长度相同，导致每一个数据的查询效率都是相同的，稳定的log(n)）
4. B+树更有利于对数据库的扫描。(B树在提高了磁盘的I/O性能的同时，并没有解决元素遍历的效率低下的问题，而B+树只需要遍历叶子节点，就可以解决对全部关键字信息的扫描。所以对于数据库中频繁使用的范围查询很快)