ToB企服应用市场:ToB评测及商务社交产业平台

标题: MySQL-06.索引的数据结构 [打印本页]

作者: 水军大提督 时间: 2024-5-17 23:30
标题: MySQL-06.索引的数据结构
1.为什么使用索引

索引是存储引擎用于快速找到数据记录的一种数据结构，就比如一本书的目录部分，通过目录中找到对应文章的页码，便可快速定位到需要的文章。MySQL中的索引也是一样的原理，举行数据查找时，起首查看查询条件是否掷中某条索引，符合则通过索引查找相关数据，如果不符合则需要全表扫描，即需要一条条的查找记录，知道找到与条件符合的记录。

上图，是在没有索引的情况下，从磁盘读取数据的示意图。建立索引的目的，就是为了减少磁盘I/O的次数，加快查询速率。
2.索引及其优缺点

2.1 索引概述

MySQL官方对索引的定义为：索引(index)是帮助MySQL高效的获取数据的数据结构。
索引的本质：索引是数据结构。可以简单理解为排好序的快速查找数据结构，满足特定查找算法。这些数据结构以某种方式指向数据，如许就可以在这些数据结构的底子上实现高效查找算法。
索引是在存储引擎中实现的，因此每种存储引擎的索引不一定完全雷同，而且每种存储引擎不一定支持所有索引类型。同时，存储引擎可以定义每个表的最大索引数和最大索引长度。所有存储引擎支持每个表至少16个索引，总索引长度至少为256字节。有些存储引擎支持更多的索引数和更大的索引长度。
2.2 优点

1.类似大学图书馆建数量索引，提高数据检索的效率，低落数据库磁盘的IO成本，这也是创建索引最主要的原因。
2.创建唯一索引，可以保证数据库表中每一行数据的唯一性。
3.在实现数据的参考完整性方面，可以加快表与表之间的连接。换句话说，对于有依赖关系的子表和父表联合查询时，可以提高查询速率。
4.在使用分组和排序子句举行数据查询时，可以显著减少查询中分组和排序的时间，低落了CPU的斲丧。

2.3 缺点

增加索引也有许多倒霉的方面，主要表现在以下几个方面

1.创建索引和维护索引要泯灭时间，而且随着数据量的增加，所泯灭的时间也会增加。
2.索引需要占磁盘空间，除了数据表占数据空间之外，每一个索引还要占一定的物理空间，存储在磁盘上，如果有大量的索引，索引文件就大概比数据文件更快的达到最大文件尺寸。
3.虽然索引大大提高了查询速率，同时却会低落更新表的速率。当对表中的数据举行增加，删除和修改时，索引也要动态维护，如许就低落了数据的维护速率。

因此，选择使用索引时，需要总和考虑索引的优点和缺点。

提示:
索引可以提高查询的速率,但是会影响插入记录的速率.这种情况下,最优解就是,先移除索引,在插入数据完成后,再建立索引,用于查询.

3.InnoDB中索引的推演

3.1 索引之前的查找

#准确匹配的例子
SELECT [列名列表] FROM 表名 WHERE 列名 = 'xxx';

复制代码

3.1.1 在一个页的查找

假设目前表的记录比力少，所有的记录都可以被存放到一个页中，在查找记录的时候可以根据搜索条件的差异分为两种情况：

以主键为搜索条件
可以在页目录中使用二分法快速定位到对应的槽，然后在遍历该槽对应分组中的记录即可快速找到指定的记录。
以其他列作为搜索条件

因为在数据页中并没有对非主键列建立所谓的页目录，所以无法通过二分法快速定位相应的槽。这种情况下只能从最小记录开始依次遍历单链表中的每条记录，然后对比每条记录是否符合搜索条件。很显然这种查找的效率非常低。
3.1.2 在很多页查找

大部分情况下我们表中存放的记录都是非常多的，需要好多的数据页来存储这些记录。在很多页中查找记录的话可以分为两个步骤。
1.定位到记录所在的页。
2.从所在的页中查找相应的数据。
在没有索引的情况下，不论是根据主键列或者其他列的值举行查找，由于我们并不能快速的定位到记录所在的页，所有只能从第一个页沿着双向链表一直往下找，在每一个页中根据我们上面的查找方法去查找对应的记录。因为要遍历所有的数据页，所以这种方式显然是超级耗时的。如果一个表有一亿条记录呢？此时索引应运而生。

3.2 设计索引

建一张表

mysql> CREATE TABLE index_demo(
-> c1 INT,
-> c2 INT,
-> c3 CHAR(1),
-> PRIMARY KEY(c1)
-> ) ROW_FORMAT = Compact;

复制代码

这个新建的表index_demo中有两个int类型的列，一个CHAR(1)类型的列，而且c1列为主键，这个表使用Compact行格式来现实存储记录的。下图，是简化index_demo表的行格式图：

record_type：记录头信息的一项属性，表示记录的类型，0表示普通记录，2表示最小记录，3表示最大记录，1暂时还没用过，背面讲。
next_record：记录头信息的一些属性，表示下一条记录的地址相对于本记录的地址偏移量，也可以简单的理解为指向下一条记录的指针。
各个列的值：这里只记录index_demo表中的三个列，c1，c2和c3。
其他信息：除了上述三种信息外的所有信息，包括其他隐藏列的值以及记录的额外信息。

将记录格式示意图的其他信息暂时去掉并把它竖起来的效果如下图

把一些记录放到页里的示意图就是:

3.2.1 一个简单的索引设计方案

我们在根据某个搜索条件查找一些记录时为什么要遍历所有的数据页呢？因为各个页中的记录并没有规律，MySQL不知道搜索条件匹配那些记录，所以不得不依次遍历所有的数据页。所以如果想快速定位到需要查找的记录在那些数据页怎么办？可以为快速定位记录所在的数据页建立一个目录，建这个目录必须满足下边这些要求。

下一个数据页中记录的主键值必须大于上一个页中用户记录的主键值

假设：每个数据页最多能存放3条记录(现实上一个数据页，可以存放很多条记录)。
向index_demo表插入3条数据

mysql> insert into index_demo(c1,c2,c3) values(1,4,'u'),(3,9,'d'),(5,3,'y');
Query OK, 3 rows affected (0.00 sec)
Records: 3 Duplicates: 0 Warnings: 0

复制代码

当下这些记录按照主键巨细串联成一个单向链表，如图所示

从图中可以看出，index_demo表中的3条记录都被插入到了编号为10(注意这个页号，其实在底层存储数据时，是一个具体的地址，比力好理解，抽象为页号)的数据页中。此时在插入一条记录。

mysql> insert into index_demo(c1,c2,c3) values(4,4,'a');
Query OK, 1 row affected (0.00 sec)

复制代码

因为假设一页只能存放3条记录，所以需要新增一个页，用于生存c1=4的数据

注意，新分配的数据页编号大概并不是连续的。它们只是通过维护者上一页和下一页的编号而建立了链表关系。别的，页10中用户记录的最大的主键值是5，而页28中有有一条记录的主键值是4，因为5>4，所以这就不符合下一个页的用户数据的主键值必须大于上一个的用户主键值(后一个页的最主键最小值大于上一个页的主键最大值)的要求，所以在插入主键值为4的记录的时候需要伴随着一次记录移动，也就是把主键值为5的记录移动到页28中，然后再把主键为4的记录插入到页10中，这个过程的示意图如下

这个过程表明了在对页中记录举行增编削查操纵的过程中，我们必须通过一些诸如记录移动的操纵来始终保证这个状态一直成立：下一个页的用户数据的主键值必须大于上一个的用户主键值。这个过程也被称为页分裂。

由于数据页的编号大概是不连续的，所以在向index_demo表中插入许多记录后，大概是如许的效果：

因为这些16KB的页在物理存储上是不连续的，所以如果想从这么多页中根据主键值快速定位某些记录所在的页，我们需要给这些页建立目录，每个目录项包括下边两个部分
1.页的用户记录中最小的主键值，用key表示。
2.页号，用page_no表示
为上边几个页做好的目录就行如许

以页28为例，它对应目录项2，这个目录项中包含着该页的页号28以及该页中用户记录的最小主键值5。我们只需要把几个目录项在物理存储器上连续存储（比如：数组），就可以实现根据主键值快速查找某条记录的功能了。
比如：查找主键值为20的记录，具体查找过程分两步：
1.先从目录项中根据二分法快速确定出主键值为20的记录在目录项3中（因为12 < 20 2）有以下的特性：
<ol>根节点的儿子数的范围是 [2,M]。
每个中间节点包含 k-1 个关键字和 k 个孩子，孩子的数量 = 关键字的数量 +1，k 的取值范围为[ceil(M/2), M]。
叶子节点包括 k-1 个关键字（叶子节点没有孩子），k 的取值范围为 [ceil(M/2), M]。

假设中间节点节点的关键字为：Key[1], Key[2], …, Key[k-1]，且关键字按照升序排序，即 Key

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/) Powered by Discuz! X3.4