Mysql索引原理

数据结构

在了解原理之前，得先科普几种数据结构

二叉排序树

通过中序遍历

需满足条件

• 若左子树不空，则左子树上所有节点的值均小于它的根节点的值
• 若右子树不空，则右子数上所有节点的值均大于它的根节点的值
• 它的左、右子树也分别为二叉排序数（递归定义）

图 001

优点

每次经过一次节点时
最多可以减少一半的可能

缺点

CASE 1

图 001中搜索值为1的节点

不过极端情况会出现所有节点都位于同一侧
直观上看就是一条直线，那么这种查询的效率就比较低了
如CASE 1会查询6次

优化（平衡树）

图 002

所谓平衡，说的是这棵树的各个分支的高度是均匀的
它的左子树和右子树的高度之差绝对值小于1
这样就不会出现一条支路特别长的情况
如图 002

于是，在这样的平衡树中进行查找时
总共比较节点的次数不超过树的高度
这就确保了查询的效率（时间复杂度为O(logn)）

CASE 1 中的查询次数就会减小到4次了

注意

具体怎么实现树平衡的
看本文的你不用深入了解
只用知道普通的树要变成平衡树，会在树的成员数量变化的时候，同时通过某些算法调整树就行了

思考优化方案

如图 002所示
因为树的节点的出度d（即，叶子节点个数）都是2
所以虽然图中只有9个节点，但是扫到关键字为1的节点要4次

对我们来说，应该先想办法把树的高度(深度，目前是4)变得矮
下面的B树就是一个初步方案

B树(B-树)

B树 的别名是 B-树 ，英文名是Balance Tree
适用于外查找的树，它是一种平衡的多叉树

图 003

需满足条件

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

此外，每个节点上，会直接存储一些数据信息

对比二叉排序平衡树

• 叶子节点个数变多了
  • 那么树的高度可能就变矮了

搜索简述

示例，这是一个三阶的B树
图 004

相比磁盘I/O的速度，内存中的比较耗时几乎可以忽略
所以只要树的高度足够低，I/O次数足够少，就可以提升查找性能

小结

现在我们树是变得矮了

示例，搜索关键字为4的节点，如图 004
我们可以直接获取到这个节点所携带的信息了

B+树

B+树是为磁盘或其他直接存取辅助设备而设计的一种平衡查找树
在B+树中，所有记录节点都是按键值的大小顺序存放在同一层的叶节点中，各叶节点指针进行连接

图 005

需满足条件

• 有n棵子树的非叶子结点中含有n个关键字（b树是n-1个），这些关键字不保存数据，只用来索引，所有数据都保存在叶子节点（b树是每个关键字都保存数据）
• 所有的叶子结点中包含了全部关键字的信息，及指向含这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接
• 所有的非叶子结点可以看成是索引部分，结点中仅含其子树中的最大（或最小）关键字
• 通常在b+树上有两个头指针，一个指向根结点，一个指向关键字最小的叶子结点
• 同一个数字会在不同节点中重复出现，根节点的最大元素就是b+树的最大元素

如图 005所示
在B+树中查询一次数据需要I/O的次数=树的高度

顺便一提

其实 跳表 很像 B+树 的搜索过程， 后文我再讲解这种数据结构吧

树的选择

大多关系型数据库会选用 B+树
是考虑磁盘读取设计的
磁盘每次读取的最小单元是页(普遍是4k大小)
前文云天河写到的磁盘I/O指的就是Mysql每次读取页的操作
为了方便Mysql在内存里识别节点信息
Mysql设计的时候，是一个节点存一页大小
要想每页能读取的节点信息越多
那么树的阶数（出度d）要尽可能的大

计算最大出度D的公式

d最大值 = floor(Pagesize/(Keysize + Datasize + Pointsize))

这样，树的高度才会越小，磁盘I/O次数就会小

对比B树与B+树

树的高度

因为B树每个节点直接包含了数据，而B+树只包含了数据地址的指针
所以B+树得出的最大出度会更大，磁盘I/O次数就会较少

B树中一次检索最多需要h-1次I/O（根节点常驻内存），渐进复杂度为O(h)=O(logdN)
一般实际应用中，出度d是非常大的数字，通常超过100，因此h非常小（通常不超过3）

范围查询

B树查询单条数据是非常快的，但是范围查询的话，每次查到一条数据后都得重新中序遍历
然而B+树的叶子节点都是有一个依据关键字大小顺序，指向下一个节点的链表连接着的，所以查范围会很方便

总结