MySQL数据库：索引的实现原理

一、什么是索引：

索引就是一种的数据结构，通过缩小一张表中需要查询的数据来加快搜索的速度。如果没有索引，数据库不得不进行全表扫描。好比书的目录，让你更快的找到内容。  

1、索引的优点： 

（1）大大减少查询需要检索的行数，加快查询速度，避免进行全表扫描，这也是创建索引的最主要的原因。

（2）如果索引的数据结构是B+树，在使用分组和排序时，可以显著减少查询中分组和排序的时间。

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

2、索引的缺点：

（1）当对表中的数据进行增加、删除和修改时，索引也要进行更新，维护的耗时随着数据量的增加而增加。

（2）索引需要占用物理空间，如果要建立聚簇索引，那么需要的空间就会更大。

3、索引的使用场景：

（1）在哪些列上面创建索引：

• WHERE子句中经常出现的列上面创建索引，加快条件的判断速度。
• 按范围存取的列或者在group by或order by中使用的列，因为索引已经排序，这样可以利用索引加快排序查询时间。
• 经常用于连接的列上，这些列主要是一些外键，可以加快连接的速度；
• 作为主键的列上，强制该列的唯一性和组织表中数据的排列结构；

（2）不在哪些列建索引？

只有很少数据值的列不应该增加索引。由于这些列的取值很少，例如性别列，在查询的结果中，结果集的数据行占了表中数据行的很大比例，即需要在表中搜索的数据行的比例很大。增加索引，并不能明显加快检索速度。

在查询中很少的列不应该创建索引。由于这些列很少使用到，但增加了索引，反而降低了系统的维护速度和增大了空间需求。

当添加索引造成修改成本的提高 远远大于 检索性能的提高时，不应该创建索引。当增加索引时，会提高检索性能，但是会降低修改性能。当减少索引时，会提高修改性能，降低检索性能。

定义为text, image和bit数据类型的列不应该增加索引。这些列的数据量要么相当大，要么取值很少。

二、常见索引类型：

常见的索引类型有：普通索引、唯一索引、主键索引、全文索引、组合索引。

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、唯一索引：

与普通索引类似，但索引列的值必须唯一，允许有空值，可以有多个NULL值。如果是组合索引，则列值的组合必须唯一，创建方法和普通索引类似。

--创建唯一性索引：
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、全文索引：

全文索引仅可用于 MyISAM 表，并只支持从CHAR、VARCHAR或TEXT类型，用于替代效率较低的like 模糊匹配操作，而且可以通过多字段组合的全文索引一次性全模糊匹配多个字段。对于大容量的数据表，生成全文索引是一个非常消耗时间和硬盘空间的做法。对于较大的数据集，将你的数据输入一个没有FULLTEXT索引的表中，然后创建索引，其速度比把数据输入现有FULLTEXT索引的速度更为快。

全文索引使用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;  --第二种方式

三、聚簇索引与非聚簇索引：

如果按照表中 数据存储的物理顺序与索引值的顺序分类，可以将索引分为聚簇索引与非聚簇索引两类。

1、聚簇索引（cluster）：

聚簇索引要求表中数据存储的物理顺序与索引值的顺序一致，一个基本表最多只能有一个聚簇索引，更新聚簇索引列上的数据时，往往导致表中记录的物理顺序的变更，代价较大，因此对于经常更新的列不宜建立聚簇索引

聚簇索引一般在下面场景使用：

（1）主键列，InnoDB存储引擎中，默认为表的主键建立一个聚簇索引。

（2）按范围存取的列或者在group by或order by中使用的列。在聚簇索引下，因为表中数据存储的物理顺序与索引的逻辑顺序一致，所以在包含范围检查(between、<、<=、>、>=)或使用group by或order by的查询时，一旦找到具有范围中第一个键值的行，具有后续索引值的行保证物理上毗连在一起而不必进一步搜索，避免了大范围扫描，可以大大提高查询速度。

（3）在连接操作中使用的列。

（4）不经常修改的列。因为码值修改后，数据行必须移动到新的位置。

2、非聚簇索引：

表中记录的物理顺序与索引值的顺序不一致的索引组织，一个基本表可以有多个聚簇索引。

四、MySQL索引的数据结构：

常见的索引的数据结构有：B+Tree、Hash索引。

1、Hash索引：

MySQL中，只有Memory存储引擎支持hash索引，是Memory表的默认索引类型。hash索引把数据以hash值形式组织起来，因此检索效率非常高，可以一次定位。

hash索引的缺点：

（1）Hash索引仅能满足等值的查询，不能满足范围查询、排序。因为数据在经过Hash算法后，其大小关系就可能发生变化。

（2）当创建组合索引时，不能只适用组合索引的部分列进行查询。因为hash索引是把多个列数据合并后再计算Hash值，所以对单独列数据计算Hash值是没有意义的。

（3）当发生Hash碰撞时，Hash索引不能避免表数据的扫描。因为仅仅比较Hash值是不够的，需要比较实际的值以判定是否符合要求。

2、B+Tree索引：

B+Tree是mysql使用最频繁的一个索引数据结构，是Innodb和Myisam存储引擎模式的索引类型。相对Hash索引，B+Tree索引在查找时需要从根节点到叶节点进行多次IO操作，在查询速度比不上Hash索引，但是更适合排序等操作。

B+Tree索引的优点(也是为什么使用B+Tree索引的主要原因)：

（1）带顺序访问指针的B+Tree：B+Tree所有索引数据都存储在叶子结点上，并且增加了顺序访问指针，每个叶子节点都有指向相邻叶子节点的指针。这样做是为了提高区间查询效率，例如查询key为从18到49的所有数据记录，当找到18后，只需顺着节点和指针顺序遍历就可以一次性访问到所有数据节点。

（2）大大减少磁盘I/O读取次数。（详细看本博客第二部分）

五、为什么使用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-Tree作为索引结构效率是非常高的。

而红黑树这种结构，虽然时间复杂度也为O(h)，但是h明显要深的多，并且由于逻辑上很近的节点，在物理上可能很远，无法利用局部性，所以IO效率明显比B树差很多。

另外，B+Tree更适合作为索引的数据结构，原因和内节点出度d有关。从上面分析可以看到，d越大索引的性能越好，而出度d的上限取决于节点内key和data的大小，由于B+Tree内节点去掉了data域，因此可以拥有更大的出度，磁盘IO的次数也就更少了。

3、B-Tree与B+Tree的对比：

根据B-Tree 和 B+Tree的结构，我们可以发现B+树相比于B树，在文件系统或者数据库系统当中，更有优势，原因如下：

（1）B+树有利于对数据库的扫描：B树在提高了磁盘IO性能的同时并没有解决元素遍历的效率低下的问题，而B+树只需要遍历叶子节点就可以解决对全部关键字信息的扫描，所以范围查询、排序等操作，B+树有着更高的性能。

（2）B+树的磁盘IO代价更低：B+树的内部结点的data域并没有存储数据，因此其内部结点相对于B树更小。如果把所有同一内部结点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多，相对来说I/O读写次数也就降低了。

（3）B+树的查询效率更加稳定：由于B+树的内部结点只是叶子结点中关键字的索引，并不存储数据。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。

六、MySQL索引的实现：

在MySQL中，索引属于存储引擎级别的概念，不同存储引擎对索引的实现方式是不同的，本部分主要讨论MyISAM和InnoDB两个存储引擎的索引实现方式。

 1、MyISAM索引的实现：

（1）主键索引：MyISAM引擎使用B+Tree作为索引结构，叶子节点的data域存放的是数据记录的地址。下图是MyISAM索引的原理图：

这里设表一共有三列，假设我们以Col1为主键，则上图是一个MyISAM表的主键索引（Primary key）示意。可以看出MyISAM的索引文件仅仅保存数据记录的地址。

（2）辅助索引：

在MyISAM中，主键索引和辅助索引在结构上没有任何区别，只是主索引要求key是唯一的，而辅助索引的key可以重复。如果我们在Col2上建立一个辅助索引，则此索引的结构如下图所示： 

同样也是一棵B+Tree，data域保存数据记录的地址。

因此，MyISAM中索引检索的算法为首先按照B+Tree搜索算法搜索索引，如果指定的Key存在，则取出其data域的值，然后以data域的值为地址，读取相应数据记录。

MyISAM的索引方式也叫做“非聚集”的，之所以这么称呼是为了与InnoDB的聚集索引区分。

2、InnoDB索引的实现：

虽然InnoDB也使用B+Tree作为索引结构，但具体实现方式与MyISAM却不相同。

（1）主键索引：

与MyISAM第一个重大区别是InnoDB的数据文件本身就是索引文件。从上文知道，MyISAM索引文件和数据文件是分离的，索引文件仅保存数据记录的地址。而在InnoDB中，表数据文件本身就是按B+Tree组织的一个索引结构，这棵树的叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键，因此InnoDB表数据文件本身就是主索引。

上图是InnoDB主索引（同时也是数据文件）的示意图，可以看到叶节点包含了完整的数据记录。这种索引叫做聚集索引，因为InnoDB的数据文件本身要按主键聚集，所以InnoDB要求表必须有主键（MyISAM可以没有），如果没有显式指定，则MySQL系统会自动选择一个可以唯一标识数据记录的列作为主键，如果不存在这种列，则MySQL自动为InnoDB表生成一个隐含字段作为主键，这个字段长度为6个字节，类型为长整形。

（2）辅助索引：

第二个与MyISAM索引的不同是InnoDB的辅助索引data域存储相应记录主键的值而不是地址。换句话说，InnoDB的所有辅助索引都引用主键作为data域。例如，下图为定义在Col3上的一个辅助索引：

这里以英文字符的ASCII码作为比较准则。聚集索引这种实现方式使得按主键的搜索十分高效，但是辅助索引搜索需要检索两遍索引：首先检索辅助索引获得主键，然后用主键到主索引中检索获得记录。不过由于辅助索引会包含主键列，所以，如果主键使用过长的字段，将会导致其他辅助索变得更大。所以争取尽量把主键定义得小一些。

 InnoDB 表是基于聚簇索引建立的。

3、小结：

（1）InnoDB索引和MyISAM索引的区别：

MyISAM和InnoDB都是使用B+树索引，MyISAM的主键索引和辅助索引的Data域都是保存行的地址，但是InnoDB的主键索引保存的不是行的地址，而是保存该行的所有所有数据，而辅助索引的Data域保存的则是主索引的值。

（2）了解不同存储引擎的索引实现方式对于正确使用和优化索引都非常有帮助，例如知道了InnoDB的索引实现后，就很容易明白为什么不建议使用过长的字段作为主键，因为所有辅助索引都引用主索引，过长的主索引会令辅助索引变得过大。再例如，用非单调的字段作为主键在InnoDB中不是个好主意，因为InnoDB数据文件本身是一颗B+Tree，非单调的主键会造成在插入新记录时数据文件为了维持B+Tree的特性而频繁的分裂调整，十分低效，而使用自增字段作为主键则是一个很好的选择。

相关博客：

https://blog.csdn.net/zhangliangzi/article/details/51366345

https://blog.csdn.net/Debug_zhang/article/details/52168552

https://blog.csdn.net/kennyrose/article/details/7532032