前言
2022/7/31 11:39
暑假学习ing
推荐
【MySQL数据库教程天花板，mysql安装到mysql高级，强！硬！-哔哩哔哩】
第06章 索引的数据结构
1. 为什么使用索引
索引是存储引擎用于快速找到数据记录的一种数据结构，就好比一本数课书的目录部分，通过目录中找到对应文章的页码，便可快速定位到需要的文章。MySQL中也是一样的道理，进行数据查找时，首先查看查询条件是否命中某条索引，符合则通过索引查找相关数据，如果不符合则需要全表扫描，即需要一条一条地查找记录，直到找到与条件符合的记录。
如上图所示，数据库没有索引的情况下，数据分布在硬盘不同的位置上面，读取数据时，摆臂需要前后摆动查找数据，这样操作非常消耗时间。如果数据顺序摆放，那么也需要从1到6行按顺序读取，这样就相当于进行了6次IO操作，依旧非常耗时。如果不借助任何索引结构帮助快速定位数据的话，我们查找col 2=89这条记录，就要逐行去查找、去比较。从Col 2= 34开始，进行比较，发现不是，继续下一行。我们当前的表只有不到10行数据，但如果表很大的话，有上千万条数据，就意味着要做很多很多次磁盘I/O才能找到。现在要查找Col 2=89这条记录。CPU必须先去磁盘查找这条记录，找到之后加载到内存，再对数据进行处理。这个过程最耗时间的就是磁盘I/O(涉及到磁盘的旋转时间（速度较快)、磁头的寻道时间(速度慢、费时))
假如给数据使用二叉树这样的数据结构进行存储，如下图所示
对字段Col 2添加了索引，就相当于在硬盘上为Col 2维护了一个索引的数据结构，即这个二叉搜索树。二叉搜索树的每个结点存储的是<K，V>结构，key 是Col 2, value是该key所在行的文件指针〈地址)。比如:该二叉搜索树的根节点就是(34,0x07)。现在对Col 2添加了索引，这时再去查找Col 2=89这条记录的时候会先去查找该二叉搜索树（二叉树的遍历查找)。读34到内存，89>34;继续右侧数据，读89到内存，89 == 89;找到数据返回。找到之后就根据当前结点的value快速定位到要查找的记录对应的地址。可以发现，只需要查找两次就可以定位到记录的地址，查询速真就提高了。
这就是为什么要建索引，目的就是 为了减少磁盘I/0的次数，加快查询速率
2. 索引及其优缺点
2.1 索引概述
MySQL官方对索引的定义为:索引(Index）是帮助MySQL高效获取数据的数据结构。
索引的本质：索引是数据结构。可以简单理解为"排好序的快速查找数据结构”，满足特定查找算法。这些数据结构以某种方式指向数据，这样就可以在这些数据结构的基础上实现高级查找算法。索引是在存储引擎中实现的，因此每种存储引擎的索引不一定完全相同，并且每种存储引擎不一定支持所有索引类型。同时，存储引挚可以定义每个表的最大索引数和最大索引长度。所有存储引擎支持每个表至少16个索引，总索引长度至少为256字节。有些存储引擎支持更多的索引数和更大的索引长度。
2.2 优点
(1)类似大学图书馆建书目索引，提高数据检索的效率，降低数据库的IO成本，这也是创建索引最主要的原因
(2）通过创建唯一索引，可以保证数据库表中每一行数据的唯一性
(3)在实现数据的参考完整性方面，可以加速表和表之间的连接。换句话说，对于有依赖关系的子表和父表联合查询时，可以提高查询速度。
(4)在使用分组和排序子句进行数据查询时，可以显著减少查找中分组和排序的时间，降低了CPU的消耗。
2.3 缺点
增加索引也有许多不利的方面，主要表现在如下几个方面:
(1）创建索引和维护索引要耗费时间，并且随着数据量的增加。所耗费的时间也会增加。
(2）索引需要占磁盘空间，除了数据表占数据空间之外，每一个索引还要占一定的物理空间，存储在磁盘上，如果有大量的索引，索引文件就可能比数据文件更快达到最大文件尺寸
(3）虽然索引大大提高了查询速度，同时却会降低更新表的速度。当对表中的数据进行增加、删除和修改的时候，索引也要动态地维护，这样就降低了数据的维护速度。
因此，选择使用索引时，需要综合考虑索引的优点和缺点。
提示:
索引可以提高查询的速度，但是会影响插入记录的速度。这种情况下，最好的办法是先删除表中的索引，然后插入数据，插入完成后再创建索引。
3. lnnoDB中索引的推演
3.1 索引之前的查找
先来看一个精确匹配的例子:
SELECT [列名列表] FROM 表名 WHERE 列名 = xxx;
1. 在一个页中的查找
假设目前表中的记录比较少，所有的记录都可以被存放到一个页中，在查找记录的时候可以根据搜索条件的不同分为两种情况:
以主键为搜索条件
可以在页目录中使用二分法快速定位到对应的值，然后再遍历该值对应分组中的记录即可快速找到指定的记录。
以其他列作为搜索条件
因为在数据页中并没有对非主键列建立所谓的页目录，所以无法通过二分法快速定位相应的值。这种情况下只能从最小记录开始依次遍历单链表中的每条记录，然后对比每条记录是不是符合搜索条件。很显然，这种查找的效率是非常低的。
2. 在很多页中查找
大部分情况下表中存放的记录都是非常多的，需要好多的数据页来存储这些记录。在很多页中查找记录的话可以分为两个步骤:
1.定位到记录所在的页
2.从所在的页内中查找相应的记录
在没有索引的情况下，不论是根据主键列或者其他列的值进行查找，由于并不能快速的定位到记录所在的页，所以只能从一个页沿着双向链表一直往下找，在每一个页中根据上面的查找方式去查找指定的记录。因为要遍历所有的数据页，所以这种方式显然是超级耗时的。如果一个表有一亿条记录呢?此时索引应运而生。
3.2 设计索引
可以先看一下第四章 存储器管理【操作系统】的分页存储管理方式
可以先看一下第七章 文件管理【操作系统】的文件目录
建一个表：
CREATE TABLE index_demo( c1 INT, c2 INT, c3 CHAR(1), PRIMARY KEY(c1) ) ROW_FORMAT = Compact;##ROW_FORMAT--行格式
这个新建的 index_demo 表中有2个INT类型的列，1个CHAR(1)类型的列，而且规定了c1列为主键，这个表使用 Compact 行格式来实际存储记录的。这里简化了index_demo表的行格式示意图：
行格式在下一章中讲到
在示意图里展示记录的这几个部分:
record_type : 记录头信息的一项属性，表示记录的类型，0表示普通记录、2表示最小记录、3表示最大记录、1表示目录项的记录，暂时还没用过，下面讲。
next_record : 记录头信息的一项属性，表示下一条地址相对于本条记录的地址偏移量，用箭头来表明下一条记录是谁。
各个列的值: 这里只记录在index_demo表中的三个列，分别是c1、c2和c3。
其他信息∶除了上述3种信息以外的所有信息，包括其他隐藏列的值以及记录的额外信息
将记录格式示意图的其他信息项暂时去掉并把它竖起来的效果就是这样：
把一些记录放到页里的示意图就是下面这个基本的数据页模型：
1. 一个简单的索引设计方案
我们在根据某个搜索条件查找一些记录时为什么要遍历所有的数据页呢？
因为各个页中的记录并没有规律，并不知道搜索条件匹配哪些页中的记录，所以不得不依次遍历所有的数据页。
所以如果想快速的定位到需要查找的记录在哪些数据页中该咋办？
可以为快速定位记录所在的数据页而建立一个目录 ，建这个目录必须满足下面一、二的规定：
- 下一个数据页中用户记录的主键值必须大于上一个页中用户记录的主键值。
假设:每个数据页最多能存放3条记录(实际上一个数据页非常大，可以存放下好多记录)。有了这个假设之后我们向index_demo表插入3条记录:
INSERT INTO index_dema VALUES ( 1,4,'u '),(3,9, 'd')， (5, 3, 'y ' );
那么这些记录已经按照主键值的大小串联成一个单向链表了，如图所示:
从图中可以看出来, index_demo表中的3条记录都被插入到了编号为10的数据页中了。此时再来插入一条记录:
INSERT INTO index _demo VALUES(4,4, 'a' };
因为页10最多只能放3条记录，所以我们不得不再分配一个新页:
注意，新分配的数据页编号可能并不是连续的。它们只是通过维护着上一个页和下一个页的编号而建立了链表关系。另外，页10中的用户记录最大的主键值是5，而页28中有一条记录的主键值是4，因为5 > 4，所以这就不符合下一个数据页中用户记录的主键值必须大于上一个页中用户记录的主键值的要求。所以在插入主键值为4的记录的时候需要伴随着一次记录移动，也就是把主键值为4的记录移动到页28中，然后再把主键值为4的记录插入到页10中，这个过程的示意图如下:
因为这些16KB的页在物理存储上是不连续的，所以如果想从这么多页中根据主键值快速定位某些记录所在页，需要给它们做个目录，每个页对应一个目录项，每个目录项包括下边两个部分:
页的用户记录中最小的主键值，用key来表示。
页号，用page_no表示。
所以为上面几个页做好的目录就像这样子:
以页28 为例，它对应目录项2 ，这个目录项中包含着该页的页号 28 以及该页中用户记录的最小主键值 5 。只需要把几个目录项在物理存储器上连续存储（比如：数组），就可以实现根据主键
值快速查找某条记录的功能了。
比如：查找主键值为 20 的记录，具体查找过程分两步：
1.先从目录项中根据二分法快速确定出主键值为20的记录在目录项3中（因为 12 < 20 < 209 ），它对应的页是页9 。
2.再根据前边说的在页中查找记录的方式去 页9 中定位具体的记录。
至此，针对数据页做的简易目录就搞定了。这个目录有一个别名，称为索引
