MySQL数据库：索引的实现原理
2022-12-08
1.什么是索引：
索引是一种数据结构，它通过减少表中需要查询的数据来加速搜索。 如果没有索引，数据库将不得不进行全表扫描。 它就像一本书的目录，让您更快地找到内容。
1、索引的优点：
（1）大大减少查询需要检索的行数，加快查询速度，避免全表扫描，这是创建索引的主要原因。
（2）如果索引的数据结构是b+树，使用分组排序时，可以显着减少查询中分组排序的时间。
(3)通过创建唯一索引，可以保证数据库表中每一行数据的唯一性。
2、索引的缺点：
(1)当对表中的数据进行增删改查时，索引也必须更新，维护时间会随着数据量的增加而增加。
(2)索引需要占用物理空间。 如果要建立聚集索引，需要的空间会更大。
3、索引使用场景：
(1) 在哪些列上创建索引：
对where子句中经常出现的列建立索引，以加快条件的判断速度。 range访问的列或者group by或order by中使用的列，因为索引已经排序，可以使用索引来加快排序查询时间。 经常用于连接列，这些列主要是一些外键，可以加快连接速度； 作为主键列，强制该列的唯一性以及组织表中数据的排列结构；
(2) 哪些列没有索引？
数据值很少的列不应该被索引。 由于这些列的值较少，例如性别列，因此在查询结果中，结果集的数据行占表中数据行的比例较大，即需要查询的数据行的比例被搜索的表非常大。 增加索引并不能明显加快检索速度。 查询中很少出现的列不应建立索引。 由于这些列很少被使用，但是索引的添加降低了系统的维护速度并增加了空间需求。 添加索引会导致修改成本的增加远远大于检索性能的增加，因此不应该创建索引。 添加索引时，检索性能会提高，但修改性能会降低。 当减少索引时，会提高修改性能，降低检索性能。 不应对定义为文本、图像和位数据类型的列建立索引。 这些列中的数据量要么非常大，要么只取很少的值。
2. 常见索引类型：
常见的索引类型有：普通索引、唯一索引、主键索引、全文索引、复合索引。
1、普通指标：
最基本的索引，没有任何限制。
--直接创建索引：
create index index_name on table(column(length);
--修改表结构的方式添加索引：
alter table table_name add index index_name on (column(length));
--创建表的时候同时创建索引：
create table ‘table’(
id int not null,
username varchar(16) not null,
index [indexname] (username(length))
); 2、唯一索引：
与普通索引类似，但索引列的值必须唯一，允许空值，并且可以有多个空值。 如果是复合索引，列值的组合必须是唯一的，创建方法与普通索引类似。
--创建唯一性索引：
create unique index indexname on mytable(username(length));
--修改表结构：
alter table table_name add unique indexname on (column(length));
--创建表的时候指定：
create table mytable(
id int not null,
username varchar(16) not null,
unique [indexname] (username(length))
); 3、主键索引：
可以理解为一种特殊的唯一索引，不允许空值。
--创建表的时候创建，当把某个列设为主键的时候,数据库会自动的创建一个以主键作为名称的主键索引。
create table table(
id int primary key auto_increment,
name varchar(32) not null)
);
--修改表结构：
alter table `table_name` add primary key ( `col` );4.全文索引：
全文索引只能用于表，并且只支持char或text类型，用于替代模糊匹配等效率较低的操作，并且可以通过multi的全文索引一次完全模糊匹配多个字段- 场组合。 对于大容量的数据表，生成全文索引是一种非常耗时且消耗硬盘空间的做法。 对于较大的数据集，将数据输入到没有索引的表中然后创建索引比将数据输入到现有索引中更快。
全文索引使用b树来存储索引数据，但它在索引之前使用特定的算法对字段数据进行分割（通常每4个字节）。 索引文件存储的是切分前的索引串集合，同样对于切分后的索引信息，btree结构对应的节点中存储的是切分后的单词信息及其在切分前的索引串集合中的位置。
–创建表的适合添加全文索引
create table `table` (
`id` int(11) not null auto_increment ,
`title` char(255) character set utf8 collate utf8_general_ci not null ,
`content` text character set utf8 collate utf8_general_ci null ,
`time` int(10) null default null ,
primary key (`id`),
fulltext (content)
);
–修改表结构添加全文索引
alter table article add fulltext index_content(content);
–直接创建索引
create fulltext index index_content on article(content);5、组合索引：（最左边前缀）
为了更多地提高mysql的效率，可以建立复合索引。 创建复合索引时，应将最常用（频率）的列作为约束放置在最左边，并且列依次递减。
--创建组合索引：
alter table `table_name` add index index_name (col1(length), col2(length), col3(length));6.显示索引信息：
可以使用show index命令列出表中的相关索引信息。 可以通过添加\g来格式化输出信息。
show index from table_name; \g........7.删除索引：
drop index [indexname] on mytable; --第一种方式
alter table testalter_tbl drop index c; --第二种方式3、聚集索引和非聚集索引：
如果按照数据在表中存储的物理顺序和索引值的顺序来分类，索引可以分为聚集索引和非聚集索引。
1、聚集索引()：
聚集索引要求表中数据存储的物理顺序与索引值的顺序一致。 一张基本表最多只能有一个聚集索引。 当更新聚集索引列上的数据时，表中记录的物理顺序经常发生变化。 ，成本较高，所以不建议对频繁更新的列建立聚集索引
聚集索引一般用于以下场景： （1）主键列，在存储引擎中，默认为表的主键创建聚集索引。 (2) 按范围访问的列或在 group by 或 order by 中使用的列。 在聚集索引下，由于表中数据存储的物理顺序与索引的逻辑顺序一致，因此当进行范围检查(,=)或者使用group by或order by进行查询时发现，一旦第一个key在范围内找到值行，后续索引值的行保证物理上连续，无需进一步搜索，避免大规模扫描，大大提高查询速度。 (3) 连接操作中使用的列。 (4) 不经常修改的列。 由于代码值被修改，数据行必须移动到新位置。
2.非聚集索引：
表中记录的物理顺序与索引值的顺序不一致的索引组织，一个基本表可以有多个聚集索引。
四、mysql索引的数据结构：
常见的索引数据结构有：b+树、哈希索引。
1、哈希索引：
在mysql中，只有存储引擎支持哈希索引，这是表的默认索引类型。 哈希索引以哈希值的形式组织数据，因此检索效率非常高，可以一次性定位。
哈希索引的缺点： (1)哈希索引只能满足等值查询，不能满足范围查询和排序。 因为数据经过哈希算法之后，它的大小关系可能会发生变化。 (2) 创建复合索引时，不能只查询复合索引的部分列。 由于哈希索引是在组合多个列数据后计算哈希值，因此针对单个列数据计算哈希值是没有意义的。 (3)当发生哈希冲突时，哈希索引无法避免对表数据的扫描。 因为仅仅比较哈希值是不够的，还需要与实际值进行比较来判断是否满足要求。
2.b+树索引：
b+tree是mysql最常用的索引数据结构，是存储引擎模式的索引类型。 与hash索引相比，b+tree索引在查找时需要从根节点到叶子节点进行多次io操作。 查询速度不如哈希索引快，但更适合排序等操作。
b+tree索引的优点（也是使用b+tree索引的主要原因）：（1）带有顺序访问指针的b+tree：b+tree的所有索引数据都存储在叶子节点上，顺序访问增加了指针，每个叶节点都有指向相邻叶节点的指针。 这样做是为了提高区间查询的效率。 例如查询key为18到49的所有数据记录，当找到18时，只需沿着节点和指针的顺序遍历即可一次性访问到所有数据节点。 (2)大大减少磁盘I/O读取次数。 （详细内容请参见本博客第二部分）
5、为什么使用b+tree作为索引：
一般来说，索引本身也很大，不可能全部存储在内存中，所以索引往往以索引文件的形式存储在磁盘上。 这种情况下，索引查找过程中会产生磁盘I/O消耗。 与内存访问相比，I/O 访问的消耗要高出几个数量级，因此评价一个数据结构作为索引的好坏最重要的指标就是在访问过程中磁盘 I/O 操作次数的渐近复杂度。抬头。 换句话说，索引的数据结构应该尽量减少搜索过程中磁盘I/O访问的次数。
下面首先介绍内存和磁盘访问的原理，然后结合这些原理来分析b+tree作为索引的效率。
1.局部性和磁盘预读的原理：
由于存储介质的特性，磁盘本身的访问速度要比主存慢很多。 再加上机械运动的成本，磁盘的存取速度往往是主存的百分之几。 因此，为了提高效率，需要尽量减少磁盘i/o。 为了达到这个目的，磁盘往往不是严格按需读取，而是每次都提前读取。 即使只需要一个字节，磁盘也会从这个位置开始，顺序向后读取一定长度的数据到内存中。 其理论基础是计算机科学中众所周知的局部性原理：当使用一条数据时，通常会立即使用附近的数据。 程序运行过程中所需的数据通常比较集中。
由于磁盘顺序读取的效率很高（不需要寻道时间，旋转时间很少），预读可以提高具有局部性的程序的 I/O 效率。 预读的长度一般为页的整数倍。 当程序要读取的数据不在主存中时，就会触发缺页异常。 这时，系统会向磁盘发出读信号，磁盘会找到数据的起始位置，连续向后读取一页或几页。 加载到内存中，然后异常返回，程序继续运行。
页是计算机管理的内存的逻辑块。 硬件和操作系统通常将主存和磁盘存储区域划分为大小相等的连续块。 每个存储块称为页（在许多操作系统中，页大小通常为4k），主存和磁盘以页为单位交换数据。
2、b+tree索引的性能分析：
如上所述，一般用磁盘i/o次数来评价索引结构的优劣。
首先，分析b树。 B 树搜索最多需要访问 h 个节点。 同时数据库巧妙地利用了磁盘预读的原理，将一个节点的大小设置为一页。 即每次创建新节点时，直接申请一个页面。 这保证了节点在物理上存储在一页中，并且计算机存储分配是页对齐的，使得每个节点只需一次I/O即可完全加载。 b树中的一次检索最多需要h-1次i/o（根节点常驻内存），时间复杂度为o(h)=o(logdn)。 一般实际应用中，出度d是一个很大的数，通常超过100，因此h很小。
综上所述，使用b树作为索引结构的效率是非常高的。
至于红黑树的结构，虽然时间复杂度也是o(h)，但是h显然要深很多，而且由于逻辑上相近的节点可能物理上距离很远，无法利用局部性，所以io的效率显然是低的比b树差很多。
另外，b+tree更适合作为索引数据结构，原因与内部节点的出度d有关。 从上面的分析可以看出，d越大，索引的性能越好，而出度d的上限取决于节点中key和数据的大小。 由于b+tree中的节点去掉了数据字段，所以可以有更大的出度速度，磁盘io的次数会更少。
3、b-tree和b+tree的比较：
根据b-tree和b+tree的结构，我们可以发现b+tree在文件系统或者数据库系统中比b-tree更有优势，原因如下：
（1）b+树有利于数据库的扫描：b树提高了磁盘io性能，并没有解决元素遍历效率低的问题，而b+树只需要遍历叶子节点就可以解决对于所有关键字信息的扫描问题，因此范围查询、排序等操作，b+树具有更高的性能。
（2）b+树的磁盘io成本较低：b+树内部节点的数据域不存储数据，因此其内部节点比b树小。 如果同一内部节点的所有关键字都存储在同一个磁盘块中，则该磁盘块可以容纳的关键字数量也更大。 一次性读入内存的需要查找的关键字越多，I/O读写次数相对减少。
（3）b+树的查询效率更稳定：因为b+树的内部节点只是叶子节点中关键字的索引，不存储数据。 所以任何关键词搜索都必须走一条从根节点到叶子节点的路径。 所有关键字查询的路径长度相同，导致每条数据的查询效率相同。
6、mysql索引的实现：
在mysql中，索引属于存储引擎级别的概念。 不同的存储引擎以不同的方式实现索引。 这部分主要讨论两种存储引擎的索引实现。
1、指标的实现：
(1)主键索引：引擎采用b+tree作为索引结构，叶子节点的data字段存储数据记录的地址。 下图是索引的示意图：
这里表一共有三列，假设我们使用col1作为主键，上图是一个表的主键索引（key）的示意图。 可见索引文件只保存了数据记录的地址。
(2)辅助索引：
中，主键索引和辅助索引在结构上没有区别，只是主索引要求键唯一，而辅助索引的键可以重复。 如果我们在col2上创建一个辅助索引，这个索引的结构如下图所示：
它也是一棵b+树，数据字段保存了数据记录的地址。
因此，索引检索算法是首先按照b+tree搜索算法来搜索索引，如果指定的key存在，则取出其数据字段的值，然后以数据字段的值作为地址来检索读取对应的数据记录。
索引的索引方式也称为“非聚集”，之所以这样称呼是为了与索引的聚集索引相区别。
2.索引的实现：
虽然也采用b+tree作为索引结构，但具体实现方法有所不同。
(1) 主键索引：
第一个大的区别是数据文件本身就是索引文件。 由上可知，索引文件和数据文件是分开的，索引文件只保存数据记录的地址。 中，表数据文件本身是一个由b+树组织的索引结构，这棵树的叶子节点的数据字段存储了完整的数据记录。 该索引的键是数据表的主键，因此表数据文件本身就是主索引。
上图是主索引（也是一个数据文件）的示意图，可以看出叶子节点包含了完整的数据记录。 这种索引称为聚集索引，因为数据文件本身是根据主键聚集的，所以表必须有主键（也可能没有），如果没有显式指定，mysql系统会自动选择某一列可以唯一标识数据记录为主键，如果没有该列，mysql会自动为表生成一个隐式字段作为主键，该字段的长度为6字节，类型为长整型。
(2)辅助索引：
与索引的第二个区别是辅助索引的数据字段存储的是相应记录主键的值而不是地址。 换句话说，所有二级索引都将主键作为数据字段。 例如，下图显示了在col3上定义的辅助索引：
这里以英文字符的ascii码作为比较标准。 聚集索引的实现使得通过主键的搜索非常高效，但是辅助索引搜索需要两次检索索引：先检索辅助索引获取主键，然后使用主键检索中的记录主索引。 但是，由于辅助索引会包含主键列，如果主键使用太长的字段，会导致其他辅助索引变大。 所以尽量将主键定义得尽可能小。
表是基于聚集索引构建的。
3、总结：
(1)指数与索引的区别：
并且都使用b+树索引。 主键索引和辅助索引的数据字段都存储行的地址，但是主键索引不保存行的地址，而是保存行的所有数据，辅助索引的数据该字段保存主索引的值。
(2)了解不同存储引擎的索引实现方法对于正确使用和优化索引非常有帮助。 例如，了解了索引的实现之后，就很容易理解为什么不建议使用太长的字段作为主键，因为所有的辅助索引都是参考主索引，太长的主索引会让辅助索引变得太大。 再比如，使用非单调字段作为主键并不是一个好主意，因为数据文件本身就是一棵b+tree，非单调主键会导致数据文件保持以下特性：插入新记录时的b+树。 拆分调整效率很低，使用自增字段作为主键是一个不错的选择。
相关博客：
