前言

很多人对数据库索引可能都是知其然却不知其所以然，对索引没有很深入的理解，在使用过程中也一知半解，导致没有办法准确高效地使用索引，甚至存在不少误用的情况，导致使用索引反而降低了系统的性能。下面就以MySQL索引为对象，通过几篇文章来带大家好好的学习下索引的知识。

索引的数据结构
索引的存储方式
索引的利弊以及高效使用

什么是索引

数据库索引指的是数据库管理系统中一个排序的数据结构，以协助快速查询、更新数据库表中的数据。简单理解就是类似书籍的目录，独立于书籍内容之外，能够快速根据目录查到到需要的文章的页码。如果没有目录，我们就要一页一页地翻页来查找文章，同理，如果没有索引的话，数据库系统只能一行一行地查找数据，注意，如果没有达到限制查找的行数，这样的遍历就要一直进行下去，直到全部遍历完。

显而易见，这样的查找效率是不可接受的。所以我们需要索引的帮助，索引可以提升数据查找的效率，从而大大提升数据库的性能。

索引分类

索引一般可以分为四类

• 单列索引：单列索引指的是只包含一列的索引，又可分为三种：
  • 普通索引：普通索引是最基本的索引类型，没有什么限制，且允许空值和重复值。
  • 唯一索引：唯一索引列中的值必须是唯一的，允许存在一个空值。多个空值仍然会视为重复
  • 主键索引：主键索引是特殊的唯一索引，不允许存在空值。
• 组合索引：组合索引也就是多列索引，由多列组合创建的索引，使用的时候遵循最左前缀原则。
• 全文索引：全文索引只有MyISAM引擎支持，且只能在CHAR,VARCHAR,TEXT类型字段上使用全文索引，主要用于做文章的关键字搜索的
• 空间索引：空间索引是对空间数据类型的字段建立的索引。

数据结构

学习MySQL索引的第一步，是先了解下MySQL索引的数据结构，也就是索引是用什么结构来存储的，了解了索引的数据结构才能帮助我们更好地理解，为什么索引有那么高效的检索性能，以及怎么样高效使用索引。

MySQL索引常见的数据存储结构有哈希结构，B+树结构，R树结构。其中R树结构用于空间索引，不常见。下面来介绍下其他两种结构。

哈希结构

结构和查找过程

哈希结构的索引是通过哈希表来保存索引的，其结构具体如下图所示：

哈希索引存储的是哈希值和链表指针，查找过程为：

• 先根据 key 的值生成对应的哈希值
• 在哈希表 buckets 中查找对应哈希值的链表指针
• 如果链表指针对应的数据行只有一行，直接返回改行，如第二个key，否则在链表中一行一行查找对应的key，如第四个key。如果找不到则返回空

在MySQL中，只有Memory引擎显式支持哈希索引，这也是Memory引擎表的默认索引类型，当然Memory也支持B+树。值得一提的是，Memory引擎是支持非唯一哈希索引的。在数据库世界里是比较与众不同，如果多个列的哈希值相同，索引会以链表的方式存放多个记录指针到同一个哈希条目中。

优势与劣势

哈希查找的过程非常快，只需要一次哈希计算就能很快找到对应的行数据。然而也因为其结构简单，所以哈希索引也有很大的限制。哈希索引的限制如下：

• 哈希索引无法用于排序，因为它本身的存储是无序的
• 哈希索引也不支持部分索引列匹配查找和模糊匹配，因为哈希索引始终是使用索引的全部列值内容来计算哈希值的。如：数据列（a,b）上建立哈希索引，如果只查询数据列a，则无法使用该索引。对于类似aa%的查询也无法使用哈希索引
• 哈希索引只支持等值匹配，不支持任何范围查询如 >。这是因为哈希索引是无序的
• 如果哈希冲突很多的话，会影响哈希索引的性能，因为每次查询或者删除修改数据的时候都需要遍历链表进行比较才能找到对应的数据

因为这些限制，哈希索引只适用于某些特定的场合。而一旦适合哈希索引，则它带来的性能提升将非常显著。举个例子，在数据仓库应用中有一种经典的“星型”schema，需要关联很多查找表，哈希索引就非常适合查找表的需求。

B+树结构

下面再来介绍下B+树结构的索引，在介绍前，我们先来了解下可以用来其他快速查找数据的树结构，以便理解为什么要用B+树。

平衡二叉排序树

平衡二叉排序树是基于二分法的策略提高数据的查找速度的二叉树的数据结构，其树高平衡，不会出现单链的情况。其结构如下所示：

平衡二叉排序树有以下特点：

• 节点最多允许两个子节点存在
• 左侧的子节点小于当前节点，右侧的子节点大于当前的节点
• 它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，且左右子树也是一棵平衡二叉排序树。

平衡二叉排序树查找数据的速度近于二分法查找O(logn)，然而二叉树搜索需要很高的I/O次数，导致性能并不如人意。这是因为每个节点存储的数据比较少，每次节点进行比较的时候都需要进行一次I/O获取节点的数据，而在操作系统中，I/O的成本是很高的，具体可以看这里 https://draveness.me/sql-index-intro/ 。为了解决I/O次数高的问题，我们就有了B树。

B树

B树又名平衡多路查找树，顾名词义，它的查找路径不止两个，也就是不止两个子节点。其结构如下：

一个 m 阶的B树是一个有以下属性的树：

• 每一个节点最多有 m 个子节点
• 每一个非叶子节点（除根节点）最少有 ⌈m/2⌉ 个子节点
• 如果根节点不是叶子节点，那么它至少有两个子节点
• 有 k 个子节点的非叶子节点拥有 k − 1 个关键字
• 所有的叶子节点都在同一层

简单来理解就是每一层节点可以拥有的子节点个数增加了，而且每一个节点携带的关键字也增加了（这样才能对应多个子节点）。例如上面第二层的第一个节点，P1指针指向的子节点都是是比 8 小的数据，P2指向的则是大于8小于12的。

B树分裂和合并
B树为了保持其结构，存在着分裂和合并的过程，以三阶的为例，假设我们要插入12 45 9 78 60 55 58，具体如下：
(1) 先插入12

(2) 再插入45

(3) 插入9，这时候第一层的关键字已经有三个了，需要分裂成两个子树

(4) 插入78

(5) 插入60，再次分裂

(6) 插入55

(7) 插入58，再次分裂

最终我们得到上面结构的B树。

删除B树里的元素的时候会触发合并操作，这里就不细讲了，有兴趣的读者可以自己查下资料。

优缺点

B树的优点是每层的节点数增加了，树高也大大减少，这就大大减少了I/O次数，读取一个节点的时候可以一次性读取大量关键字数据。另外数据库可以充分利用了磁盘块读写的原理（磁盘数据存储是采用块的形式存储的，每个块的大小为4K，每次IO进行数据读取时，同一个磁盘块的数据可以一次性读取出来），把节点大小限制和充分使用在磁盘块大小范围内，这样能大大提高对数据读取的效率。

B树相比二叉树虽好，但还是存在以下问题：
1.每个节点中既要存索引信息，又要存其对应的数据，如果数据很大，那么当树的体量很大时，每次读到内存中的树的信息就会不太够。
2.B树遍历整个树的过程和二叉树本质上是一样的，B树相对二叉树虽然提高了磁盘IO性能，但并没有解决遍历元素效率低下的问题。

为了解决这些问题，也就有了我们今天的主角：B+树

B+树

B+树是B树的升级版，更充分地利用了节点的空间。其结构如下：

和B树的主要区别如下：

• 有 k 个子节点的非叶子节点拥有 k 个关键字，B树是k-1个。这使得非叶子节点能保存的关键字大大增加，因此树高也大大降低。
• 关键字不保存数据，只是用来索引，这样非叶子节点的所占的内存空间就变小了，读到内存中的索引信息就会更多一些，相当于减少了磁盘IO次数
• 数据都是存在叶子节点，这样保证了相近的数据都能存在同一块数据块里。另外也使得B+树的查询次数更稳定，每次查询次数都是相同的，需要查询到叶子节点
• 叶子节点的指针指向下一个数据对应的叶子节点，因此B+树具备了天然排序功能，在排序和范围查找的时候更方便，可以通过叶子节点的指针找到下一个叶子节点的位置
• B+树可以方便地做全表搜索，只需要从第一个叶子节点顺序往后面扫描即可，而B树则需要做树的遍历。

参考资料

《高性能MySQL》
https://blog.csdn.net/apt1203JN/article/details/79587593
https://blog.csdn.net/zk3326312/java/article/details/79377680
https://www.cnblogs.com/shan1393/p/8999622.html

Enjoy it !

如果觉得文章对你有用，可以赞助我喝杯咖啡~

版权声明

转载请注明作者和文章出处
作者: X先生
首发于https://www.jianshu.com/p/2de74601db7a