mysql 索引原理与B+Tree 作者:马育民 • 2022-04-14 23:31 • 阅读:10065 关于索引详见:[MySQL索引](https://www.malaoshi.top/show_1EF4uz5d3l26.html "MySQL索引") # 说明 索引的本质是数据结构,本文讲解mysql 索引原理与B+Tree # 顺序访问 [![](/upload/0/0/1IX3aTcGKB37.png)](/upload/0/0/1IX3aTcGKB37.png) 顺序访问是在表中进行 **全表扫描**,从头到尾逐行遍历,直到找到符合条件的数据。 **优点:**实现比较简单 **缺点:**当表中有大量数据的时候,**效率非常低下** # 二叉树 使用 **二叉树** 存储 `age` 列的数据,查找速度会快很多,如下: [![](/upload/0/0/1IX3btl5bJFM.png)](/upload/0/0/1IX3btl5bJFM.png) ### 缺点 根据 [数据结构:二叉排序树(二叉查找树)](https://www.malaoshi.top/show_1IX3cJo0to5t.html "数据结构:二叉排序树(二叉查找树)") 的缺点,需要用到 **平衡二叉树** # 平衡二叉树 详见 [数据结构:平衡二叉树AVL](https://www.malaoshi.top/show_1IX3cKvWVkEq.html "数据结构:平衡二叉树AVL") ### 缺点 根据上文的缺点,需要用到 **红黑树** # 红黑树 详见 [数据结构:红黑树](https://www.malaoshi.top/show_1IX3chtv6Ld6.html "数据结构:红黑树") ### 缺点 根据上文的缺点,需要用到 **B树** # B树 详见 [数据结构:B-树](https://www.malaoshi.top/show_1IX3dMSM34jy.html "数据结构:B-树") ### 缺点 根据上文的缺点,需要用到 **B+树** # B+树 详见 [数据结构:B+树](https://www.malaoshi.top/show_1IX3doDYCXUY.html "数据结构:B+树") # B+树索引 上面 `user` 表数据,放在了 `user.ibd` 文件中 ### 数据页 在表中,每行记录看起来是挨在一起的。但在 `user.ibd` 文件中,他们被分成很多小份的 **数据页**,每份大小 `16k`,如下: [![](/upload/0/0/1IX3eYgKlXpQ.png)](/upload/0/0/1IX3eYgKlXpQ.png) ### 数据页的组成 [![](/upload/0/0/1IX3eYoFXi5j.png)](/upload/0/0/1IX3eYoFXi5j.png) ##### 页头 整个页 `16k`,较小,但表中一行行的数据多,一页肯定放不下,所以会分开放到很多页里。为了唯一标识具体是哪一页,给每一页编上号码,即: **页号**(其实是一个表空间的地址偏移量)。 同时为了把这些数据页给关联起来,于是引入了前后指针,用于指向前后的页。这些都被加到了页头里。 ##### 校验码 向某数据页写数据时,写一半断电,会造成数据损坏。 所以为了保证数据页的正确性,引入了校验码。这个被加到了页尾。 ##### 保存行记录 剩下的空间,才是用来放一行行的数据。 ##### 页目录 而record如果行数特别多的话,进入到页内时挨个遍历,效率也不太行,所以为这些数据生成了一个 **页目录**,通过 **二分查找** 的方式将查找效率从 `O(n)` 变成 `O(lgn)`。 # 从页到索引 ### 笨方法 如果想查一行记录,可以读取每一页,再把里面的 数据 读取出来挨个判断是不是要找的。 行数量小的时候,这么操作也没啥问题。 ##### 缺点 行数量大了,性能就慢了 ### 加索引 于是为了加速搜索,在每个数据页里选出 **主键id最小的记录**,而且只需要它们的 **主键id和所在页的页号**。组成新的记录,放入到一个新生成的一个数据页中,这个新数据页跟之前的页结构没啥区别,而且大小还是16k。 但为了跟之前的数据页进行区分。数据页里加入了 **页层级(page level)**的信息,从 `0` 开始往上算。于是页与页之间就有了 **上下层级**的概念,就像下面这样: [![](/upload/0/0/1IX3eYw2eph0.png)](/upload/0/0/1IX3eYw2eph0.png) 页跟页之间看起来就像是一棵倒过来的树了,即:`B+树` 索引。 最下面那一层,page level 为0,也就是所谓的叶子结点,其余都叫非叶子结点。 ### 三层B+树 上面展示的是两层的树,如果数据变多了,我们还可以再通过类似的方法,再往上构建一层。就成了三层的树。 [![](/upload/0/0/1IX3eYyM6rq6.png)](/upload/0/0/1IX3eYyM6rq6.png) 那现在我们就可以通过这样一棵B+树加速查询 # 查询 查找数据5 [![](/upload/0/0/1IX3eZ1XK89K.png)](/upload/0/0/1IX3eZ1XK89K.png) 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 原文出处:http://malaoshi.top/show_1IX38GULUJ0D.html