时间：2021-07-01 10:21:17 帮助过：37人阅读
——索引优化，可以说是数据库相关优化、理解尤其是查询优化中最常用的优化手段之一。所以，只有深入索引的实现原理、存储方式、不同索引间区别，才能设计或使用最优的索引，最大幅度的提升查询效率！ 一、BTree索引 1、概述 Mysql数据库中使用最频繁的索引
——索引优化，可以说是数据库相关优化、理解尤其是查询优化中最常用的优化手段之一。所以，只有深入索引的实现原理、存储方式、不同索引间区别，才能设计或使用最优的索引，最大幅度的提升查询效率！
一、BTree索引
1、概述
Mysql数据库中使用最频繁的索引类型，基本所有存储引擎都支持BTree索引。正是其优异的检索表现，才使其有这样的地位。
2、存储结构
正如其名，这类索引的物理文件大多就是以BTree结构来存储的，但会有不同的存储引擎在使用BTree索引时，对存储结构稍作修改，比如MyISAM存储引擎，使用B+Tree的数据结构，它相对与BTree结构，所有的数据都存放在叶子节点上，且把叶子节点通过指针连接到一起，形成了一条数据链表，以加快相邻数据的检索效率。
（对B树、B+树不熟悉的，可参看博客索引基础——B-Tree、B+Tree、红黑树、B*Tree数据结构 或《算法导论》）
另外，对于innoDB存储引擎，虽然同样使用B+Tree作为索引的存储结构，但具体实现却与MyISAM截然不同，这也是作为MyISAM与InnoDB存储引擎的一个重要区别反复被面试官问到。（关于MyISAM与InnoDB存储引擎可参看博客MySQL架构设计——MyISAM存储引擎与InnoDB存储引擎）
（1）MyISAM引擎索引结构的叶子节点的数据域，存放的并不是实际的数据记录，而是数据记录的地址。索引文件与数据文件分离，这样的索引称为“非聚簇索引”。MyISAM的主索引与辅助索引区别并不大，只是主键索引不能有重复的关键字。
如下图所示为非聚簇索引的主键索引：
其检索算法：先按照B+Tree的检索算法检索，找到指定关键字，则取出对应数据域的值，作为地址取出数据记录。
（2）InnoDB引擎索引结构的叶子节点的数据域，存放的就是实际的数据记录（对于主索引，此处会存放表中所有的数据记录；对于辅助索引此处会引用主键，检索的时候通过主键到主键索引中找到对应数据行），或者说，InnoDB的数据文件本身就是主键索引文件，这样的索引被称为“聚簇索引”，一个表只能有一个聚簇索引。
如下图所示为聚簇索引的主键索引：
二、Hash索引
1、概述及存储结构
主要就是通过Hash算法（常见的Hash算法有直接定址法、平方取中法、折叠法、除数取余法、随机数法），将数据库字段数据转换成定长的Hash值，与这条数据的行指针一并存入Hash表的对应位置；如果发生Hash碰撞（两个不同关键字的Hash值相同），则在对应Hash键下以链表形式存储。
检索算法：在检索查询时，就再次对待查关键字再次执行相同的Hash算法，得到Hash值，到对应Hash表对应位置取出数据即可，如果发生Hash碰撞，则需要在取值时进行筛选。目前使用Hash索引的数据库并不多，主要有Memory等。
2、Hash索引的弊端
一般来说，索引的检索效率非常高，可以一次定位，不像B-Tree索引需要进行从根节点到叶节点的多次IO操作。有利必有弊，Hash算法在索引的应用也有很多弊端。
a、Hash索引仅仅能满足等值的查询，范围查询不保证结果正确。因为数据在经过Hash算法后，其大小关系就可能发生变化。
b、Hash索引不能被排序。同样是因为数据经过Hash算法后，大小关系就可能发生变化，排序是没有意义的。
c、Hash索引不能避免表数据的扫描。因为发生Hash碰撞时，仅仅比较Hash值是不够的，需要比较实际的值以判定是否符合要求。
d、Hash索引在发生大量Hash值相同的情况时性能不一定比B-Tree索引高。因为碰撞情况会导致多次的表数据的扫描，造成整体性能的低下，可以通过采用合适的Hash算法一定程度解决这个问题。
e、Hash索引不能使用部分索引键查询。因为当使用组合索引情况时，是把多个数据库列数据合并后再计算Hash值，所以对单独列数据计算Hash值是没有意义的。
三、Full-Text索引
1、概述
全文索引，目前MySQL中只有MyISAM存储引擎支持，并且只有CHAR、VARCHAR、TEXT类型支持。它用于替代效率较低的LIKE模糊匹配操作，而且可以通过多字段组合的全文索引一次性全模糊匹配多个字段。
2、存储结构
同样使用B-Tree存放索引数据，但使用的是特定的算法，将字段数据分割后再进行索引（一般每4个字节一次分割），索引文件存储的是分割前的索引字符串集合，与分割后的索引信息，对应Btree结构的节点存储的是分割后的词信息以及它在分割前的索引字符串集合中的位置。
四、索引利弊
1、索引的好处
a、提高数据检索的效率，降低检索过程中必须要读取得数据量，降低数据库IO成本。
b、降低数据库的排序成本。因为索引就是对字段数据进行排序后存储的，如果待排序的字段与索引键字段一致，就在取出数据后不用再次排序了，因为通过索引取得的数据已满足排序要求。另外，分组操作是先排序后分组，所以索引同样可以省略分组的排序操作，降低内存与CPU资源的消耗。
2、索引的弊端
a、索引会增加 增、删、改操作所带来的IO量与调整索引的计算量。
b、索引要占用空间，随着数据量的不断增大，索引还会带来存储空间的消耗。
五、判断是否应该建索引的条件
1、较频繁的作为查询条件的字段应该创建索引
2、唯一性太差的字段不适合单独创建索引，即使频繁作为查询条件
3、增、删、改操作较多的数据库字段不适合建索引
附：计算机内存存取、磁盘存取原理：（转载自：张洋的博客园http://www.uml.org.cn/sjjm/201107145.asp）
目前计算机使用的主存基本都是随机读写存储器（RAM），现代RAM的结构和存取原理比较复杂，这里本文抛却具体差别，抽象出一个十分简单的存取模型来说明RAM的工作原理。
图1
从抽象角度看，主存是一系列的存储单元组成的矩阵，每个存储单元存储固定大小的数据。每个存储单元有唯一的地址，现代主存的编址规则比较复杂，这里将其简化成一个二维地址：通过一个行地址和一个列地址可以唯一定位到一个存储单元。图5展示了一个4 x 4的主存模型。
主存的存取过程如下：
当系统需要读取主存时，则将地址信号放到地址总线上传给主存，主存读到地址信号后，解析信号并定位到指定存储单元，然后将此存储单元数据放到数据总线上，供其它部件读取。
写主存的过程类似，系统将要写入单元地址和数据分别放在地址总线和数据总线上，主存读取两个总线的内容，做相应的写操作。
这里可以看出，主存存取的时间仅与存取次数呈线性关系，因为不存在机械操作，两次存取的数据的“距离”不会对时间有任何影响，例如，先取A0再取A1和先取A0再取D3的时间消耗是一样的。
上文说过，索引一般以文件形式存储在磁盘上，索引检索需要磁盘I/O操作。与主存不同，磁盘I/O存在机械运动耗费，因此磁盘I/O的时间消耗是巨大的。
图6是磁盘的整体结构示意图。
图2
一个磁盘由大小相同且同轴的圆形盘片组成，磁盘可以转动（各个磁盘必须同步转动）。在磁盘的一侧有磁头支架，磁头支架固定了一组磁头，每个磁头负责存取一个磁盘的内容。磁头不能转动，但是可以沿磁盘半径方向运动（实际是斜切向运动），每个磁头同一时刻也必须是同轴的，即从正上方向下看，所有磁头任何时候都是重叠的（不过目前已经有多磁头独立技术，可不受此限制）。
图7是磁盘结构的示意图。
图3
盘片被划分成一系列同心环，圆心是盘片中心，每个同心环叫做一个磁道，所有半径相同的磁道组成一个柱面。磁道被沿半径线划分成一个个小的段，每个段叫做一个扇区，每个扇区是磁盘的最小存储单元。为了简单起见，我们下面假设磁盘只有一个盘片和一个磁头。
当需要从磁盘读取数据时，系统会将数据逻辑地址传给磁盘，磁盘的控制电路按照寻址逻辑将逻辑地址翻译成物理地址，即确定要读的数据在哪个磁道，哪个扇区。为了读取这个扇区的数据，需要将磁头放到这个扇区上方，为了实现这一点，磁头需要移动对准相应磁道，这个过程叫做寻道，所耗费时间叫做寻道时间，然后磁盘旋转将目标扇区旋转到磁头下，这个过程耗费的时间叫做旋转时间。
由于存储介质的特性，磁盘本身存取就比主存慢很多，再加上机械运动耗费，磁盘的存取速度往往是主存的几百分分之一，因此为了提高效率，要尽量减少磁盘I/O。为了达到这个目的，磁盘往往不是严格按需读取，而是每次都会预读，即使只需要一个字节，磁盘也会从这个位置开始，顺序向后读取一定长度的数据放入内存。这样做的理论依据是计算机科学中著名的局部性原理：
当一个数据被用到时，其附近的数据也通常会马上被使用。
程序运行期间所需要的数据通常比较集中。
由于磁盘顺序读取的效率很高（不需要寻道时间，只需很少的旋转时间），因此对于具有局部性的程序来说，预读可以提高I/O效率。
预读的长度一般为页（page）的整倍数。页是计算机管理存储器的逻辑块，硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块，每个存储块称为一页（在许多操作系统中，页得大小通常为4k），主存和磁盘以页为单位交换数据。当程序要读取的数据不在主存中时，会触发一个缺页异常，此时系统会向磁盘发出读盘信号，磁盘会找到数据的起始位置并向后连续读取一页或几页载入内存中，然后异常返回，程序继续运行。
到这里终于可以分析B-/+Tree索引的性能了。
上文说过一般使用磁盘I/O次数评价索引结构的优劣。先从B-Tree分析，根据B-Tree的定义，可知检索一次最多需要访问h个节点。数据库系统的设计者巧妙利用了磁盘预读原理，将一个节点的大小设为等于一个页，这样每个节点只需要一次I/O就可以完全载入。为了达到这个目的，在实际实现B-Tree还需要使用如下技巧：
每次新建节点时，直接申请一个页的空间，这样就保证一个节点物理上也存储在一个页里，加之计算机存储分配都是按页对齐的，就实现了一个node只需一次I/O。
B-Tree中一次检索最多需要h-1次I/O（根节点常驻内存），渐进复杂度为O(h)=O(logdN)。一般实际应用中，出度d是非常大的数字，通常超过100，因此h非常小（通常不超过3）。
综上所述，用B-Tree作为索引结构效率是非常高的。
而红黑树这种结构，h明显要深的多。由于逻辑上很近的节点（父子）物理上可能很远，无法利用局部性，所以红黑树的I/O渐进复杂度也为O(h)，效率明显比B-Tree差很多。
上文还说过，B+Tree更适合外存索引，原因和内节点出度d有关。从上面分析可以看到，d越大索引的性能越好，而出度的上限取决于节点内key和data的大小：
dmax = floor(pagesize / (keysize + datasize + pointsize)) (pagesize – dmax >= pointsize)
或
dmax = floor(pagesize / (keysize + datasize + pointsize)) - 1 (pagesize – dmax < pointsize)
floor表示向下取整。由于B+Tree内节点去掉了data域，因此可以拥有更大的出度，拥有更好的性能。
这一章从理论角度讨论了与索引相关的数据结构与算法问题，下一章将讨论B+Tree是如何具体实现为MySQL中索引，同时将结合MyISAM和InnDB存储引擎介绍非聚集索引和聚集索引两种不同的索引实现形式。
