mysql 索引原理与B+Tree

关于索引详见:MySQL索引

说明

索引的本质是数据结构,本文讲解mysql 索引原理与B+Tree

顺序访问

顺序访问是在表中进行 全表扫描,从头到尾逐行遍历,直到找到符合条件的数据。

优点:实现比较简单

缺点:当表中有大量数据的时候,效率非常低下

二叉树

使用 二叉树 存储 age 列的数据,查找速度会快很多,如下:

缺点

根据 数据结构:二叉排序树(二叉查找树) 的缺点,需要用到 平衡二叉树

平衡二叉树

详见 数据结构:平衡二叉树AVL

缺点

根据上文的缺点,需要用到 红黑树

红黑树

详见 数据结构:红黑树

缺点

根据上文的缺点,需要用到 B树

B树

详见 数据结构:B-树

缺点

根据上文的缺点,需要用到 B+树

B+树

详见 数据结构:B+树

B+树索引

上面 user 表数据,放在了 user.ibd 文件中

数据页

在表中,每行记录看起来是挨在一起的。但在 user.ibd 文件中,他们被分成很多小份的 数据页,每份大小 16k,如下:

数据页的组成

页头

整个页 16k,较小,但表中一行行的数据多,一页肯定放不下,所以会分开放到很多页里。为了唯一标识具体是哪一页,给每一页编上号码,即: 页号(其实是一个表空间的地址偏移量)。

同时为了把这些数据页给关联起来,于是引入了前后指针,用于指向前后的页。这些都被加到了页头里。

校验码

向某数据页写数据时,写一半断电,会造成数据损坏。
所以为了保证数据页的正确性,引入了校验码。这个被加到了页尾。

保存行记录

剩下的空间,才是用来放一行行的数据。

页目录

而record如果行数特别多的话,进入到页内时挨个遍历,效率也不太行,所以为这些数据生成了一个 页目录,通过 二分查找 的方式将查找效率从 O(n) 变成 O(lgn)

从页到索引

笨方法

如果想查一行记录,可以读取每一页,再把里面的 数据 读取出来挨个判断是不是要找的。

行数量小的时候,这么操作也没啥问题。

缺点

行数量大了,性能就慢了

加索引

于是为了加速搜索,在每个数据页里选出 主键id最小的记录,而且只需要它们的 主键id和所在页的页号。组成新的记录,放入到一个新生成的一个数据页中,这个新数据页跟之前的页结构没啥区别,而且大小还是16k。

但为了跟之前的数据页进行区分。数据页里加入了 页层级(page level)的信息,从 0 开始往上算。于是页与页之间就有了 上下层级的概念,就像下面这样:

页跟页之间看起来就像是一棵倒过来的树了,即:B+树 索引。

最下面那一层,page level 为0,也就是所谓的叶子结点,其余都叫非叶子结点。

三层B+树

上面展示的是两层的树,如果数据变多了,我们还可以再通过类似的方法,再往上构建一层。就成了三层的树。

那现在我们就可以通过这样一棵B+树加速查询

查询

查找数据5

  1. 先从顶层页的开始,记录里包含了主键id和页号(页地址)

  2. 看下图黄色的箭头,向左最小id是 1 ,向右最小id是 7。那 id=5 的数据如果存在,那必定在 左边 箭头。于是顺着的记录的页地址就到了 6 号数据页里

  3. 再判断 id=5 大于 4,所以肯定在 右边 的数据页里,于是加载 105 号数据页。在数据页里找到 id=5 的数据行,完成查询。

注意:页号并不是连续的,它们在磁盘里也不一定是挨在一起的。

优点

由于此处树的高度是 3,所以查询了 3个页,那么最多需要经历 3次磁盘IO查询

B+树最大记录数量

参考

https://blog.csdn.net/nandao158/article/details/114065093
https://mp.weixin.qq.com/s/XX_NkIIf_PLyU4IE6lEEYQ


原文出处:https://malaoshi.top/show_1IX38GULUJ0D.html