索引是对数据库表中一个或多个列的值进行排序的结构。使用索引可以快速访问数据库表中的特定信息。可以在数据库索引和一本书的目录之间进行类比。通过一本书的目录，我们可以快速找到章节位置。如果没有目录，我们只能一页页翻看。索引数据结构有很多索引结构可以用来提高查询效率。常见的有B树索引、哈希索引和B+树索引。接下来我们将对这些索引一一进行介绍，并说明InnoDB为什么使用B+树作为索引。磁盘IO文件存储在硬盘上。当前硬盘的读取速度非常有限，因此在查询定位某些数据时，应尽可能减少磁盘I/O次数。磁盘预读由于存储介质的特性，磁盘本身的访问要比主存慢很多。除了机械运动的成本外，磁盘的存取速度往往是主存的百分之几。因此，为了提高效率，尽量减少磁盘I/O。为了达到这个目的，磁盘往往不是严格按需读取，而是每次都提前读取。即使只需要一个字节，磁盘也会从这个位置开始，依次向后读取一定长度的数据到内存中。其理论依据是计算机科学中众所周知的局部性原则：当使用一条数据时，通常会立即使用附近的数据。程序运行过程中需要的数据通常比较集中。局部性原则：CPU在访问内存时，无论是访问指令还是访问数据，访问的存储单元都倾向于聚集在一个较小的连续区域内。预读的长度一般是页的整数倍。页是计算机管理的内存的逻辑块。硬件和操作系统通常将主内存和磁盘存储区域划分为大小相等的连续块。每个存储块称为一个页（在许多操作系统中，一个页的大小通常为4k），主存和磁盘以页为单位交换数据。当程序要读取的数据不在主存中时，会触发缺页异常。这时，系统会向磁盘发送一个读信号，磁盘会找到数据的起始位置，并不断地向后读取一页或几页。载入内存，然后异常返回，程序继续运行。磁盘预读的合理使用一般来说，索引本身太大，无法存储在内存中，因此索引往往以索引文件的形式存储在磁盘上。在这种情况下，索引搜索过程中会产生磁盘I/O消耗。与内存访问相比，I/O访问的消耗要高出几个数量级，所以作为指标评价一个数据结构好坏最重要的指标就是查找时的磁盘I/O操作次数。换句话说，索引结构组织应该尽量减少搜索过程中的磁盘I/O访问次数。如果能合理利用磁盘预读的特性，让每次磁盘IO读取的page中的数据都是有用的，就可以大大提高数据的查询效率。B-tree索引B-tree可以看作是二叉搜索树的扩展。B-tree允许每个节点有M-1个子节点。B树具有以下特点：根节点至少有两个子节点；每个节点包含M-1条数据，节点中的数据安装索引按升序排列；节点中至多有M个指针指向下一层节点，这些指针位于节点的多个数据之间，且下一层节点的所有数据值都大于左边的数据指针的一侧小于指针右侧的数据；每个节点至少包含M/2条数据；接下来，我们使用下例中的用户数据来构建一个B-tree，如表所示，用户数据包括姓名、性别、年龄三个字段，我们使用用户的年龄作为数据库的主键（假设age是唯一的），那么构建的B-tree的结构如下图所示。姓名陈二张三李四王吴赵刘孙启周后记吴九正氏性别男女男女年龄51020283556258090！[B-TreeIndex]与普通的二叉树相比，B-tree的一个节点存储了更多的数据，可以有效减少数据查找过程中的磁盘IO次数：二叉树的每个节点只存储一个数据，节点之间是用指针关联的，节点之间的空间是离散的，所以每个节点对应一个磁盘IO，查找一个数据的IO次数为O($log_2$N)；B树的节点可以存放M-1条数据，如果M-1条数据可以放在一个页面中，那么B树查找一次数据的IO次数为O($log_M$N)；哈希索引哈希索引是基于哈希表实现的，只有与索引的所有列完全匹配的查询才有效。哈希表是一种以键值对（Key-Value）方式存储数据的结构，用户可以在O(1)时间复杂度内根据Key找到对应的Value。哈希表通常是一个数组，可以根据索引值安装哈希算法计算出数据在数组中的位置。如果两个数据的索引值的计算位置相同，那么通常可以使用链地址法来解决冲突（其他还有其他方法解决地址冲突，比如打开自定义方法，链地址法、公共溢出区法、重新散列法等）。如下表数据所示，我们还是按照用户的年龄对用户数据进行索引（假设用户的年龄不会相同），我们使用的hash算法是addr=age%10，我们可以创建一个长度为10的数组作为hash，根据hash函数，将用户一个一个放入hash表中，当根据年龄查找用户时，可以直接计算出用户所在的位置，得到用户信息。得到的哈希表和查询过程如下图所示。姓名：陈二、张三、李四、王五、赵六、孙琦、周跋、吴九、郑氏、性别、男、女、男、女、男、男、男、男、男、男,male,male,age,age510,20,28,355,625,8090。哈希索引有以下优点：占用的额外空间小，为数据创建新的哈希索引所需的额外空间为O(N)，与索引字段的长度无关；查询速度极快，在hash函数合理的情况下，程序可以在O(1)次磁盘IO次数内找到数据；哈希索引有以下缺点：不能进行范围查询，索引的顺序在哈希过程中已经丢失；无法对数据进行排序和搜索，例如搜索最早的用户；不能使用部分索引搜索，如前缀查询等；当hash函数不合理时，会造成Hash冲突，导致查询效率低下；B+树索引InnoDB使用的索引的数据结构是一棵B+树，数据库表定义中的每一个索引对应一棵B+树，默认的聚簇索引也是一棵B+树。B+树具有以下特点：所有节点关键字按递增顺序排列，并遵循左小右大的原则；非叶子节点的子节点个数在1到M之间（下图中M为3），空树除外；非叶子节点的索引个数大于等于ceil(M/2)且小于等于M；所有叶子节点都在同一层，叶子节点之间有从左到右的指针；数据存储在叶子节点中，非叶子节点只存储索引；接下来，我们使用几个样本用户数据来构建一个B+树。如表所示，用户数据包含三个字段：姓名、性别和年龄。我们使用用户的年龄作为数据库的主键（假设年龄是唯一的），那么构建的B+树的结构如下图所示。姓名：陈二、张三、李四、王五、赵六、孙琦、周跋、吴九、郑氏、性别、男、女、男、女、男、男、男、男、男、男,age,510,20,28,355,625,8090B+树型索引数据结构有以下优点：查询性能稳定，查询一条数据所需的IO次数往往是树的高度;范围查询是有效的。安装索引范围查询时，可以先找到第一条符合条件的数据，然后向后遍历，直到第一条不符合条件的数据。中间数据均符合要求。要求;查询效率高，往往一次数据查询只需要2~3倍的磁盘IO；叶子节点存放所有数据，不需要到B+树外找数据；为什么InnoDB使用B+树在InnoDB引擎中，我们为数据库创建的索引都是以B+树的形式存在的。为什么InnoDB不使用哈希索引或B树索引？主要是基于以下原因：数据库查询经常出现非等价查询，哈希索引在这种情况下无法工作；与B树相比，B+树索引不在非叶子节点存储数据，因此一次IO可以在磁盘中读取更多的索引数据，可以有效减少磁盘IO次数；数据库查询往往会有范围查询，B+树底部的叶子节点按顺序排列，可以更有效地实现范围查询；auto-incrementprimarykeys从上面我们知道B+树需要维护索引的顺序。当用户向B+树中插入数据时，如果插入点对应的节点有空闲空间，则只需要移动该节点中的数据，将要插入的数据放入B+树中即可；当用户向B+树中插入数据时，如果插入点对应的节点没有空闲空间，则需要生成一个新节点并将部分数据移动到那里；这种情况不仅会影响插入效率，还会降低空间利用率，因为分裂节点只有部分数据；当用户删除B+树中的数据时，如果该节点或相邻节点的数据量是非常小，那么只需要直接删除数据，然后按移动节点中的其他数据；当用户删除B+树中的数据时，如果该节点和相邻节点的数据量很小，那么删除后可能需要合并该节点和相邻节点，以提高空间利用率；基于B+树需要维护索引顺序的特性，我们对索引字段提出如下建议：对于插入大量数据的场景，主键索引字段最好自增。每次自增主键追加操作插入一条新记录，不涉及移动其他记录，也不会触发叶子节点的分裂。主键索引的长度应尽可能小。主键长度越小，普通索引的叶子节点越小，普通索引占用的空间也越小。在InnoDB中，我们应该尽量使用自增主键，其优点是插入效率高，占用空间小。数据空洞和重建索引数据空洞当你修改InnoDB时，比如删除一些行，这些行只是被标记为“已删除”，但并没有从索引中物理删除，所以空间并没有真正被使用。释放回收。InnoDB的Purge线程会异步清理这些无用的索引键和行，但是释放出来的空间仍然没有返回给操作系统重新使用，这样会造成页面出现很多空洞。如果表结构包含动态长度字段，那么这些空洞甚至可能不会被InnoDB重用来存储新行，因为空间空间长度不足。数据空洞带来的问题：删除表中的数据后，表占用的空间并不会变小，造成空间浪费；会降低数据查询的速度，因为空洞会占用页面空间；我们可以使用如下SQL查看数据库的空洞大小，执行语句如下，返回结果中的DATA_FREE表示表中空闲数据块的大小。从information_schema.tables中选择data_length、data_free，其中table_schema='test'和table_name='test'；重建索引当一个表的索引中存在过多的数据空洞时，会影响SQL语句的执行效率。这时候，我们需要清理这些数据是空的。清理数据空洞比较好的方法是重建索引，因为在重建索引的过程中，会根据索引的大小对索引进行排序，然后再建立索引，而建立的索引会相对袖珍的。有什么方法可以重建索引吗？我们更直观的想法肯定是先删除索引，再重建索引。但是，无论删除主键还是创建主键，都会重建整个表。所以如果这两条语句连续执行，第一条语句就白做了。改变表user_info删除主键；改变表user_info添加主键（id）；在InnoDB中，可以通过以下语句重建表的所有索引来转换数据引擎。这是因为在数据引擎转换的过程中（即使没有真正的转换），表中的所有数据都会被读取和重写，在这个过程中会释放漏洞。需要注意的是，通过这种方式重建索引需要很长时间。改变表测试引擎=innodb
