Mysql索引原理

2019-12-19 10:04:07 Mysql 5293 0

数据结构

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

二叉排序树

通过中序遍历

需满足条件

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


图 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+树是基于磁盘存储读取设计的数据结构

树的选择

大多关系型数据库会选用 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+树的叶子节点都是有一个依据关键字大小顺序,指向下一个节点的链表连接着的,所以查范围会很方便

总结
数据库 选用树 查询的时间复杂度 原因
MongoDB B树 最多h-1次,渐进复杂度为O(h)=O(logd N) B树 恰好 key 和 data 域聚合在一起
Mysql B+树 固定为 O(logd N) a.内节点无 data 域,每个节点能索引的范围更大更精确 b.指针串在一起,这样就很容易的进行区间遍历甚至全部遍历
注:若无特殊说明,文章均为云天河原创,请尊重作者劳动成果,转载前请一定要注明出处