为什么使用索引

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

如上图所示，数据库没有索引的情况下，数据分布在硬盘不同的位置上面，读取数据时，摆臂需要前后摆动查找数据，这样操作非常消耗时间。如果数据顺序摆放，那么也需要从1到6行按顺序读取，这样就相当于进行了6次I/O操作，依旧非常耗时。如果我们不借助任何索引结构帮助我们快读定位数据的话，我们查找Col2 = 89这条记录，就要逐行去查找、去比较。从Col2 = 34开始，进行比较，发现不是，继续下一行。我们当前的表只有不到10行数据，但如果表很大的话，有上千万条数据，就意味着要做很多很多磁盘I/O才能找到。现在要查找Col2 = 89这条记录，CPU必须先去磁盘找到这条记录，找到之后加载到内存，再对数据进行处理。这个过程最耗时间的就是磁盘I/O（涉及到磁盘的旋转时间（速度较快），磁头的寻道时间（速度慢、费时））。

假如给数据使用二叉树这样的数据结构进行存储，如下图所示：

对字段Col2添加了索引，就相当于在磁盘上位Col2维护了一个索引的数据结构，即这个二叉搜索树。二叉搜索树的每个节点存储的是(k,v)结构，key是Col2，value是该key所在行的文件指针（地址）。比如：该二叉搜索树的根节点就是(34,0x07)。现在对Col2添加了索引，这时再去查找Col2 = 89这条记录的时候会先去查找该二叉搜索树（二叉树的遍历查找）。读34到内存，89＞34；继续再右侧数据，读89到内存，89=89；找到数据返回。找到之后就根据当前节点的value快速定位到要查找的记录对应的地址。我们可以发现，只需要查找两次就可以定位到记录的地址，查询速度就提高了。

这就是我们为什么要建索引，目的就是为了减少磁盘I/O的次数，加快查询速度。

补充笔记：注意是目的是为了减少磁盘I/O的次数；

减少磁盘I/O的次数的意义远大于内存层面上的算法的优化（比如时间复杂度）

索引及其优缺点

索引概述

MySQL官方对索引的定义为：索引（Index）是帮助MySQL高效获取数据的数据结构。

索引的本质：索引是数据结构。你可以简单理解为“排好序的快速查找数据结构”，满足特定查找算法。这些数据结构以某种方式指向数据， 这样就可以在这些数据结构的基础上实现高级查找算法。

索引是在存储引擎中实现的，因此每种存储索引不一定完全相同，并且每种存储引擎不一定支持所有索引类型。同时，存储引擎可以定义每个表的最大索引数和最大索引长度。所有存储引擎支持每个表至少16个索引，总索引长度至少256字节。有些存储引擎支持更多的索引数和更大的索引长度。

优点

1. 类似大学图书馆建书目索引，提高数据检索的效率，降低 数据库的IO成本 ，这也是创建索引最主要的原因。

2. 通过创建唯一索引，可以保证数据库表中每一行 数据的唯一性 。

3. 在实现数据的参考完整性方面，可以 加速表和表之间的连接 。换句话说，对于有依赖关系的子表和父表联合查询时，可以提高查询速度。

4. 在使用分组和排序子句进行数据查询时，可以显著 减少查询中分组和排序的时 间 ，降低了CPU的消耗。

缺点

增加索引也有许多不利的方面，主要表现在如下几个方面：

1. 创建索引和维护索引要耗费时间 ，并且随着数据量的增加，所耗费的时间也会增加。

2. 索引需要占磁盘空间 ，除了数据表占数据空间之外，每一个索引还要占一定的物理空间， 存储在磁盘上 ，如果有大量的索引，索引文件就可能比数据文件更快达到最大文件尺寸。

3. 虽然索引大大提高了查询速度，同时却会 降低更新表的速度 。当对表中的数据进行增加、删除和修改的时候，索引也要动态地维护，这样就降低了数据的维护速度。

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

存储结构

数据库的存储结构：页

索引结构给我们提供了高效的索引方式，不过索引信息以及数据记录都是保存在文件上的，确切说是存储在页结构中。另一方面，索引是在存储引擎中实现的，MySQL服务器上的存储引擎负责对表中数据的读取和写入工作。不同存储引擎中存放的格式一般是不同的，甚至有的存储引擎比如Memory都不用磁盘来存储数据。

由于InnoDB是MySQL的默认存储引擎，所以本章剖析InnoDB存储引擎的数据存储结构。

磁盘与内存交互基本单位：页

InnoDB将数据划分为若干个页，InnoDB中页的大小默认为16KB。

以页作为磁盘和内存之间交互的基本单位，也就是一次最少从磁盘中读取16KB的内容到内存中，一次最少把内存中的16KB内容刷新到磁盘中。也就是说，在数据库中，不论读一行，还是读多行，都是将这些行所在的页进行加载。也就是说，数据库管理存储空间的基本单位是页（Page），数据库I/O操作的最小单位是页。一个页中可以存储多个行记录。

页的大小

不同的数据库管理系统（简称DBMS）的页大小不同。比如在MySQL的InnoDB存储引擎中，默认页的大小是16KB，我们可以通过下面的命令来进行查看：

 mysql> show variables like '%innodb_page_size%';

SQL Server中页的大小为8KB，而在Oracle中我们用术语“块”（Block）来代表“页”，Oracle支持的块大小为2KB、4KB、8KB、16KB、32KB和64KB。

页的上层结构

另外在数据库中，还存在着区（Extent）、段（Segment）和表空间（Tablespace）的概念。行、页、区、段、表空间的关系如下图所示：

区（Extent）是比页大一级的存储结构，在InnoDB存储引擎中，一个区会分配64个连续的页。因为InnoDB中的页大小默认是16KB，所以一个区的大小是64*16KB=1MB。

段（Segment）由一个或多个区组成，区在文件系统是一个连续分配的空间（在InnoDB中是连续的64个页)，不过在段中不要求区与区之间是相邻的。段是数据库中的分配单位，不同类型的数据库对象以不同的段形式存在。当我们创建数据表、索引的时候，就会相应创建对应的段，比如创建一张表时会创建一个表段，创建一个索引时会创建一个索引段。

表空间（Tablespace）是一个逻辑容器，表空间存储的对象是段，在一个表空间中可以有一个或多个段，但是一个段只能属于一个表空间。数据库由一个或多个表空间组成，表空间从管理上可以划分为系统表空间、用户表空间、撤销表空间、临时表空间等。

页的内部结构

页如果按类型划分的话，常见的有数据页（保存B+树节点）、系统页、Undo页和事务数据页等。数据页是我们最常使用的页。

数据页的16KB大小的存储空间被划分为七个部分，分别是文件头（File Header）、页头（Page Header）、最大/最小记录（Infimum+supremum）、用户记录（User Records）、空闲空间（Free Space）、页目录（Page Directory）和文件尾（File Trailer）。

这7个部分作用分别如下，我们简单梳理如下表所示：

Page Directory（页目录）

在页中，记录是以单向链表的形式进行存储的。单向链表的特点就是插入、删除非常方便，但是检索效率不高，最差的情况下需要遍历链表上的所有节点才能完成检索。因此在页结构中专门设计了页目录这个模块，专门给记录做一个目录，通过二分查找法的方式进行检索，提升效率。

方式1：顺序查找

从Infimum记录（最小记录）开始，沿着链表一直往后找，总有一天会找到（或者找不到），在找的时候还能投机取巧，因为链表中各个记录的值是按照从小到大顺序排列的，所以当链表的某个节点代表的记录的主键值大于你想要查找的主键值时，你就可以停止查找了，因为该节点后边的节点的主键值依次递增。

如果一个页中存储了非常多的记录，这么查找性能很差。

方式2：使用页目录，二分法查找

1. 将所有的记录分成几个组，这些记录包括最小记录和最大记录，但不包括标记为“已删除”的记录。

2. 第1组，也就是最小记录所在的分组只有1个记录；最后一组，就是最大记录所在的分组，会有1-8条记录；其余的组记录数量在4-8条之间。

   这样做的好处是，除了第1组（最小记录所在组）以外，其余组的记录数会尽量平分

3. 在每个组中最后一条记录的头信息中会存储该组一共有多少条记录，作为n_owned字段

4. 页目录用来存储每组最后一条记录的地址偏移量，这些地址偏移量会按照先后顺序存储起来，每组的地址偏移量页被称之为槽（slot），每个槽相当于指针指向了不同组的最后一个记录。

从图中我们需要注意这么几点：

现在页目录部分中有两个槽，也就意味着我们的记录被分成了两个组，槽1中的值是112，代表最大记录的地址偏移量（就是从页面的0字节开始数，数112个字节）；槽0中的值是99，代表最小记录的地址偏移量。

注意最小和最大记录的头信息中n_owned属性

最小记录的n_owned值为1，这就代表着以最小记录结尾的这个分组中只有1条记录，也就是最小记录本身

最大记录n_owned值为5，这就代表着以最大记录结尾的这个分组中只有5条记录，包括最大记录本身还有我们自己插入的4条记录

页目录分组的个数如何确定？

为什么最小记录的n_owned值为1，而最大记录的n_owned值为5呢？

InnoDB规定，对于最小记录所在的分组只能有1条记录，最大记录所在的分组拥有记录条数只能在1-8之间，剩下的分组中记录的条数范围只能在4-8条之间。

分组是按照下边的步骤进行的：

• 初始情况下，一个数据页里只有最小记录和最大记录两条记录，它们分属于两个分组

• 之后每插入一条记录，都会从页目录中找到主键值比本记录的主键值大并且差值最小的槽，然后把该槽对应的记录的n_owned值加1，表示本组内又添加了一条记录，直到该组中的记录数等于8个

• 在一个组中的记录数等于8个后再插入一条记录时，会将组中的记录拆分成两个组，一个组中4条记录，另一个5条记录。这个过程会在页目录中新增一个槽来记录这个新增分组中最大的那条记录的偏移量