Mysql简易索引方案分析

Mysql简易索引方案分析

Mysql简易索引

一、没有索引的时候如何查找

先忽略掉索引这个概念，如果现在直接要查某条记录，要如何查找呢？

在一个页中查找

如果表中的记录很少，一个页就够放，那么这时候有 2 种情况：

用主键为搜索条件：这时就是之前文章提过的方式，页面目录中用二分法快速定位到槽，然后遍历该槽对应分组的记录，最终找到指定记录。用其他非主键的列为搜索条件：因为数据页中没有为非主键列建立页目录，无法通过二分法快速定位槽，只能从 Infimum 记录开始一次遍历单链表的每条记录，效率低下。

在很多页中查找

当表中的记录非常多，就会用到很多的数据页来存储，这时候需要 2 个步骤：

定位到记录所在页。重复上述在一个页中查找的过程。

总得来说，当没有索引，我们无法快速定位到记录所在页，只能从第一页沿着双向链表(页有前一页和后一页)一直找下去，然后在每一页中重复上述的过程查询指定的记录，需要遍历所有记录，这种方式非常耗时。

二、一个简易索引

既然是因为页数太多导致定位记录太慢，那如何解决呢？不妨参考一下“页目录”。

页目录就是为了根据主键快速定位一条记录在页中的位置而设置的。因此，我们可以探讨一种方法，即创建一个“其他目录”来快速定位记录所在的页面。

但是这个“别的目录”要想完成还得干好 2 件事。

1. 下一页用户记录的主键值必须大于上一页的

假设，每个数据页最多可以放 3 条记录(实际上可以放很多)，那么现在向表里插入 3 条记录，每条记录有3个列 c1、c2、c3。为了看着方便，存储行格式也简化下，只留关键属性。虚拟记录Infimum和Supremum分别位于用户记录的首尾，中间有3条用户记录。

此时，继续插入 1 条记录。在假设的情况下，需要至少分配一个新页面，因此这两个页面将被重新分配并重新排列。

请注意红色字体显示的两条记录，其中包括了一个新插入的主键为 4 的记录，应该被放在新页上。但是，为了满足下一页用户记录的主键值必须大于上一页的用户记录主键值，做了诸如记录移动的操作，这个过程也可以称为“页分裂”。

另外，为什么新页是页 28，而不是 11？因为页在磁盘上可能并不挨着，它们只是通过维护上一页和下一页的编号而建立了链表关系。

2. 给所有的页建立一个目录项

现在继续向表里增加数据，最终多个页的关系是这样：

为了从多个不相邻的页面快速定位某个记录，需要为它们编制一个目录，因为这些页面在磁盘上可能不是连续的。

每个页对应一个目录项，每个目录项包括：

页的用户记录中最小的主键值，用 key 来表示页号，用 page_no 表示

所以，给它们编好目录之后就是这样的关系：

那么，现在我想查找主键值为 20 的记录，具体就分两步走：

利用二分法从目录项中快速确定主键值为 20 的记录在目录项 3，并且它所在的页码为 9。知道是在页 9，重复之前的方式，找到最终目标记录。

到此，一个简易的方案完成。而完成的这个简易目录，它有个别名，叫做索引。

三、简易索引暴露出的问题

上述的简易索引是原书作者为了循序渐进的帮助读者理解而设置的内容，这并不是innodb的索引方案。

那么针对上述的建议索引，看下有哪些问题。

问题一：

InnoDB 使用页作为管理存储空间的基本单位，也就是最多只能保存16kb的连续存储。

当表中记录越来越多，此时就需要非常大的连续存储空间才可以把所有的目录项都装下，这对大数据量的表来说不现实。

问题二：

我们经常还要对记录执行增删改操作，会牵一发而动全身。

比如，上图中我如果把页 28 中的记录都删除，那么页 28 就没必要存在，进而目录项 2 也没必要存在。这时候就需要把目录项 2 后的目录项都向前移动一下。

就算不移动，把目录项 2 作为冗余放在目录项列表中，仍然会浪费很多的存储空间。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。