索引?

MySQL官方对索引的定义为:索引(Index)是帮助MySQL高效获取数据的数据结构。我们可以简单理解为:快速查找排好序的一种数据结构。

下面是一张未做任何操作的表,Col1为自增主键,Col2为Value

未加索引

此时我想查找值为22的那一行记录,因为表中值未被排序,所以只能从头遍历5次才能查找到主键为5,值为22的那一行记录。如果表中不止这7条数据,而是百万条、千万条记录呢?查询速度可想而知的慢

索引数据结构:

  • 二叉排序树
  • 红黑树
  • B树(B-Tree)
  • B+树(B+Tree)

二叉排序树

一个节点只能有两个子节点,也就是度最大为2
左节点比父亲小,右节点比父亲大

排序后

此时再对22进行Find只需要查找一次,进行一次磁盘IO便能找到需要的值。
经过二叉排序树优化后,查询效率相对于之前大大提升,但是有一种情况,如果Col2是持续递增的呢

持续递增

此时这只排序二叉树出现的失衡,也就是相当于变成了一条单向链表,如果想要查询某个值时,只能从头往下遍历查找,而不能像上面的排序二叉树一样排除掉一部分值

红黑树

红黑树的出现就可以解决这个问题,红黑树的特点会自动平衡树

未平衡

已平衡

左图在插入数值为3时,红黑树的算法发现有偏向,就会重新调整树结构

那我们可以看看,之前的数据1~6持续递增的树,会变成什么样?
1-6红黑树

经过红黑树自平衡后,现在查找6这个节点,只需要查找3次,有部分数据被提前排序了。红黑树很好的平衡了树的偏向问题,但红黑树问题也比较大。

  1. 每次都要检查规则,再把树进行重新平衡,这个是非常消耗时间的
  2. 数据量大的话,红黑树的深度会比较深,树一旦深就代表着我们读取磁盘次数就会增加

B-Tree(多路自平衡查找树,目的降低树高,减少磁盘IO)

影响数据查询时间的是树的高度,高度越高,我们需要比较的次数越多,磁盘IO操作就会越多,注意一个索引不是一次性全部加载到内存,如果索引太大比如100G一次性加载到内存也不现实,磁盘有预读机制,每次读的时候都是加载一个磁盘页(4kb)到内存里面,那我们是不是可以想办法把树的高度弄低点?那我们的B树数据结构就由此产生。

假如当前有一颗m阶的B树(注意阶的意思是指每个节点的孩子节点的个数),那么其符合

(1)每个节点最多有m个子节点
(2)除了根节点和叶子节点之外,其他的每个节点最少有m/2(向上取整)个孩子节点
(3)根节点至少有两个孩子节点,(除了第一次插入的时候,此时只有一个节点,根节点同时是叶子节点)
(4)所有的叶子节点都在同一层
(5)有k个子节点的父节点包含k-1个关键码
(6)所有的叶节点都在同一层
(7)每个节点中的子节点都是从左到右排序的

B Tree

我们的主要目标就是把树的高度弄低,上图中,我们可以看到之前的一个节点里面多了几个子节点(即几阶树)【核心点一】,这样的设计就是把之前节点只存储1个数值,现在可以存储多个数值;

多个子节点数值都是从左到右排序【核心点二】,有便于快速查找;

而且叶节点具有相同的深度,保证了每个数值查询效率一致【核心点三】

图中每个节点里面都包含具体信息data【核心点四】data类似于这个值在磁盘上的一个指针引用的地址,再查询的时候找到对应的索引后,直接取出这个节点中的信息;

B树的核心思想就是把树高度弄低,用了树节点包含多个子节点的设计思想,上图中一个树节点包含3个子节点。

1-6 B-Tree:
1-6 B-Tree

B+Tree(B-Tree变种)

非叶子结点不存储data,只存储索引(冗余),可以放更多的索引
叶子结点包含所有索引字段
叶子结点用指针连接,提高区间访问的性能

B+ Tree

一个树节点我们应该尽可能的包含更多的子节点,但又不能超过一个磁盘页(4kb)的大小,所以将所有data信息都移动了子节点中,而且子节点和子节点之间会有个指针指向,这个也是B+树的核心点,这样可以大大提升范围查询效率,也方便遍历整个树。

1-6 B+Tree

最后修改:2021 年 05 月 07 日 09 : 51 PM
如果觉得我的文章对你有用,请随意赞赏