索引的定义

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

本质上，索引的目的是为了提高查询效率，通过不断地缩小想要获取数据的范围来筛选出最终想要的结果，同时把随机的事件变成顺序的事件，也就是说，有了这种索引机制，我们可以总是用同一种查找方式来锁定数据。

可以类比银行的保险柜，比如你要找归属你的保险柜子。如果没有索引，你需要拿着钥匙，一个个的保险柜的试过去才能找到属于你的保险柜。但是如果有了索引，而且保险柜能够以物理分区的方式存在在对应的区域，同时你可以根据钥匙上的编号（A1003-10-17），找到保险柜所在 A1003 的存放房间，找到存放室保险柜的第 10 排，再找到第 17 个位置，找到属于你的保险柜，这个定位就快很多了。在没有索引的情况下，要想完成这个事情还是比较困难的。

索引的原理

除了保险柜之外，生活中可以引出很多类似的索引例子，如字典词典的目录、图书馆的检索录、火车的座次表等。

它们的原理一致：不断地缩小数据范围来筛选数据，并把随机数据变成顺序数据，方便我们更快地锁定数据。

这种索引的理解同样适用我们的数据库查询，但是数据库会有很多更复杂的情况，除了等值查询外，还有范围查询(>、<、between、in)、模糊查询(like)、并集查询(or)、交集查询（and）等等。这就要求数据库选择更加复杂和成熟的方式来应对所有问题。

根据我们上面保险柜的案例，可以对数据按照一定规则进行拆分，这样匹配的范围就降低了，但是这远远不够满足数据库复杂的查询要求。于是，数据库系统的设计者从查询算法的角度进行优化。

其中最基本的查询算法是顺序查找（linear search），这种算法复杂度为 O(n)，在数据量很大时就很不理想了，而且数据量越大，计算越复杂。

但没关系，强大的计算机科学提供了更多优秀的查找算法，比如二分查找（binary search）、二叉树查找（binary tree search）等。

但是这些查找算法都要求应用于特定的数据结构之上，如二分查找要求被检索数据有序，而二叉树查找只能基于二叉查找树结构上操作， 数据本身的组织结构不可能完全满足各种数据结构，理论上也无法同时要求将多列都按顺序进行组织。

因此， 在数据之外，数据库系统还维护着满足特定查找算法的数据结构，这些数据结构以某种方式引用（指向）数据，这样就可以在这些数据结构上实现高级查找算法。这种数据结构，就是索引。

这与上面 MySQL 官方对索引的定义遥相呼应了。

看下面的图：

图举例了一种索引方式。右边是一个数据表，这边一共模拟了两列七行的数据， 字段 1 的是数据记录的物理地址（实际应用中逻辑上相邻的记录在磁盘上并不一定物理相邻，这边主要为了举例）。为了加快 字段 2 的查找，可以维护一个左边所示的二叉查找树，每个节点分别包含索引键值和一个指向对应数据记录物理地址的指针，这样就可以运用二叉查找在 O(log2n)O(log2n)的复杂度内获取到相应数据。

这是索引的一种表现形式，但是实际的数据库系统中比较普遍是采用 B+树来实现的。B+树中的 B 代表平衡（balance），不是二叉（binary）。因为 B+树是从最早的平衡二叉树演化而来的，所以我们可以先了解下二叉查找树、平衡二叉树（AVLTree）和平衡多路查找树（B-Tree），因为 B+树是由这些树逐步演进而来。

二叉查找树

二叉树具有以下性质：左子树的键值小于根的键值，右子树的键值大于根的键值。 所以左中右是依次递增的一个过程。

如下图所示就是一棵二叉查找树，

观察该二叉树有有如下发现，深度为 1 的节点的查找次数为 1，深度为 2 的查找次数为 2，深度为 n 的节点的查找次数为 n，因此其平均查找次数为 (1+2+2+3+3+3+3) / 7 = 2.4 次。

二叉查找树也可以是如下结构（同样满足二叉树 左 < 中 < 大的特性），同样是 7,21,35,42,51,77,89 这七个数字，也可以按照下图的方式来构造：

但是这棵二叉树的查询效率就低了，平均查找次数为(1+2+3+4+5+6+6)/7=3.8 次。

因此若想二叉树的查询效率尽可能高，需要这棵二叉树是平衡的 ，从而引出新的定义：AVL 树（即平衡二叉树）。

平衡二叉树（AVL Tree）

平衡二叉树（AVL 树）在符合二叉查找树的条件下， 还满足任何节点的两个子树的高度最大差为 1。 下面的两张图片，左边是 AVL 树，它的任何节点的两个子树的高度差<=1；右边的不是 AVL 树，其根节点的左子树高度为 3，而右子树高度为 1，高度差>1；

同理，在平衡二叉树进行插入或删除节点，也可能导致 AVL 树失去平衡，这种失去平衡的二叉树可以有四种状态：LL（左左）、RR（右右）、LR（左右）、RL（右左）。

看下图示：

我们来逐一看下这几种状态。

LL（LeftLeft），即 左左。 是指插入或删除一个节点后，根节点的左孩子（Left Child）的左孩子（Left Child）还有非空节点，导致根节点的左子树比右子树高度>1，AVL 树失去平衡。

RR（RightRight），即 右右。 是指插入或删除一个节点后，根节点的右孩子（Right Child）的右孩子（Right Child）还有非空节点，导致根节点的右子树比左子树高度>1，AVL 树失去平衡。

LR（LeftRight），即 左右。 插入或删除一个节点后，根节点的左孩子（Left Child）的右孩子（Right Child）还有非空节点，导致根节点的左子树比右子树高度>1，AVL 树失去平衡。

RL（RightLeft），即 右左。 插入或删除一个节点后，根节点的右孩子（Right Child）的左孩子（Left Child）还有非空节点，导致根节点的右子树比左子树高度>1，AVL 树失去平衡。

失去平衡的 AVL 树，可以通过旋转来修复，旋转的本质是将树的节点进行调整，达到恢复平衡的目的。下面逐一来看下。

LL 的旋转： LL 失去平衡的情况下，可以通过一次旋转让 AVL 树恢复平衡。步骤如下：

1、将根节点的左孩子作为新根节点。

2、将新根节点的右孩子作为原根节点的左孩子。

3、将原根节点作为新根节点的右孩子。

如下图所示：

RR 的旋转： RR 失去平衡的情况下，旋转方法与 LL 旋转相反，步骤如下：

1、将根节点的右孩子作为新根节点。

2、将新根节点的左孩子作为原根节点的右孩子。

3、将原根节点作为新根节点的左孩子。

如下图所示：

LR 的旋转： LR 失去平衡的情况下，需要进行两次旋转，步骤如下：

1、围绕根节点的左孩子进行 RR 旋转。

2、围绕根节点进行 LL 旋转。

如下图所示，它转了两次，最后恢复成一棵 AVL 树：

RL 的旋转： RL 失去平衡的情况下也需要进行两次旋转，旋转方法与 LR 旋转相反，步骤如下：

1、围绕根节点的右孩子进行 LL 旋转。

2、围绕根节点进行 RR 旋转。

如下图所示，它转了两次，最后恢复成一棵 AVL 树：

平衡多路查找树（B-Tree）

我们知道，磁盘这种存储设备是以磁盘块（block）为基本单位的，而 B-树也是基于这种存储方式设计的平衡查找树。

所以当我们从系统磁盘读取数据时，以磁盘块（block）为基本单位映射到内存中，位于同一个磁盘块中的数据会被一次性读取出来，而不是只取需要的数据。InnoDB 存储引擎中有页（Page）的概念，页是其磁盘管理的最小单位。InnoDB 存储引擎中默认每个页的大小为 16KB，可通过参数 innodb_page_size 将页的大小设置为 4K、8K、16K，我们可以在命令窗口输入以下脚本查看：

1 mysql> show variables like 'innodb_page_size';2 +------------------+-------+3 | Variable_name | Value |4 +------------------+-------+5 | innodb_page_size | 16384 |6 +------------------+-------+7 1 row in set

而系统一个磁盘块的存储空间往往没有这么大，因此 InnoDB 每次申请磁盘空间时都会是若干地址连续磁盘块来达到页的大小 16KB。

InnoDB 在把磁盘数据读入到磁盘时会以页为基本单位，在查询数据时如果一个页中的每条数据都能有助于定位数据记录的位置，

这将会减少磁盘 I/O 次数，提高查询效率。

B-Tree 结构的数据可以让系统高效地找到数据所在的磁盘块。为了描述 B-Tree，首先定义一条记录为一个二元组[key, data] ，key 为记录的键值，对应表中的主键值，data 为一行记录中除主键外的数据。对于不同的记录，key 值互不相同。

一棵 m 阶的 B-Tree 有如下特性：

1. 每个节点最多有 m 个孩子。

2. 除了根节点和叶子节点外，其它每个节点至少有 Ceil(m/2)个孩子。

3. 若根节点不是叶子节点，则至少有 2 个孩子

4. 所有叶子节点都在同一层，且不包含其它关键字信息

5. 每个非终端节点包含 n 个关键字信息（P0,P1,…Pn, k1,…kn）

6. 关键字的个数 n 满足：ceil(m/2)-1 <= n <= m-1

7. ki(i=1,…n)为关键字，且关键字升序排序。

8. Pi(i=1,…n)为指向子树根节点的指针。P(i-1)指向的子树的所有节点关键字均小于 ki，但都大于 k(i-1)

B-Tree 中的每个节点根据实际情况可以包含大量的关键字信息和分支，如下图所示为一个 3 阶的 B-Tree：

每个节点占用一个盘块的磁盘空间，一个节点上有两个升序排序的关键字和三个指向子树根节点的指针，指针存储的是子节点所在磁盘块的地址。两个键值数据划分成的三个范围域对应三个指针指向的子树的数据的范围域。以根节点为例，两个键值数据为 33 和 66，P1 指针指向的子树的数据范围为小于 33，P2 指针指向的子树的数据范围为 33~66 之间，P3 指针指向的子树的数据范围为大于 66。

模拟查找关键字 55 的过程：

1、根据根节点找到磁盘块 Disk1，读入内存。第 1 次操作磁盘 I/O。

2、比较键值 55 在区间（33,66），找到磁盘块 Disk1 的指针 P2。

3、根据 P2 指针找到磁盘块 Disk3，读入内存。第 2 次操作磁盘 I/O。

4、比较键值 55 在区间（39,62），找到磁盘块 Disk3 的指针 P2。

5、根据 P2 指针找到磁盘块 Disk8，读入内存。第 3 次操作磁盘 I/O。

6、在 Disk8 中的键值列表中找到关键字 55。

通过上面的操作过程，发现需要 3 次磁盘 I/O 操作，和 3 次内存查找操作。由于内存中的关键字是一个有序表结构， 可以利用二分法查找提高效率。而 3 次磁盘 I/O 操作是影响整个 B-Tree 查找效率的决定因素。

B-Tree 相对于 AVLTree 缩减了节点个数，使每次磁盘 I/O 取到内存的数据都发挥了作用，从而提高了查询效率。

B+Tree

B+Tree 是在 B-Tree 基础上的一种优化，使其更适合实现外存储索引结构，InnoDB 存储引擎就是用 B+Tree 实现其索引结构。

从上面的 B-Tree 结构图中可以看到每个节点中不仅包含数据的 key 值，还有 data 值。而每一个页的存储空间是有限的，如果 data 数据较大时将会导致每个节点（即一个页）能存储的 key 的数量很小，当存储的数据量很大时同样会导致 B-Tree 的深度较大，增大查询时的磁盘 I/O 次数，进而影响查询效率。在 B+Tree 中，所有数据记录节点都是按照键值大小顺序存放在同一层的叶子节点上，而非叶子节点上只存储 key 值信息，这样可以大大加大每个节点存储的 key 值数量，降低 B+Tree 的高度，提高查找效率。

B+Tree 相比较于 B-Tree 的不同点：

1、非叶子节点只存储键值信息。

2、所有叶子节点之间都有一个链指针。

3、数据记录都存放在叶子节点中。

将上面的 B-Tree 优化，由于 B+Tree 的非叶子节点只存储键值信息，假设每个磁盘块能存储 4 个键值及指针信息，则变成 B+Tree 后其结构如下图所示：

通常在 B+Tree 上有两个头指针，一个指向根节点，另一个指向关键字最小的叶子节点，而且所有叶子节点（即数据节点）之间是一种链式环结构。因此可以对 B+Tree 进行两种查找运算：一种是对于主键的范围查找和分页查找，另一种是从根节点开始，进行随机查找。

可能上面例子中只有 22 条数据记录，看不出 B+Tree 的优点，下面做一个推算：

InnoDB 存储引擎中页的大小为 16KB，一般表的主键类型为 INT（占用 4 个字节）或 BIGINT（占用 8 个字节），指针类型也一般为 4 或 8 个字节，也就是说一个页（B+Tree 中的一个节点）中大概存储 16KB/(8B+8B)=1K 个键值（因为是估值，为方便计算，这里的 K 取值为〖10〗^3）。也就是说一个深度为 3 的 B+Tree 索引可以维护 10^3 * 10^3 * 10^3 = 10 亿 条记录。

实际情况中每个节点可能不能填充满，因此在数据库中，B+Tree 的高度一般都在 2~4 层。mysql 的 InnoDB 存储引擎在设计时是将根节点常驻内存的，也就是说查找某一键值的行记录时最多只需要 1~3 次磁盘 I/O 操作。

数据库中的 B+Tree 索引可以分为聚集索引（clustered index）和辅助索引（secondary index）。上面的 B+Tree 示例图在数据库中的实现即为聚集索引，聚集索引的 B+Tree 中的叶子节点存放的是整张表的行记录数据。辅助索引与聚集索引的区别在于辅助索引的叶子节点并不包含行记录的全部数据，而是存储相应行数据的聚集索引键，即主键。当通过辅助索引来查询数据时，InnoDB 存储引擎会遍历辅助索引找到主键，然后再通过主键在聚集索引中找到完整的行记录数据。

总结

根据上面，二叉查找树，红黑树等数据结构也可以用来实现索引，但是文件系统及数据库系统普遍采用 B+Tree 作为索引结构（ 目前 MySQL 的 MYISAM 和 INNODB 都是采用 B+Tree 作为索引结构 ），这是因为 B+Tree 索引的设计是以计算机磁盘存储结构为理论基础的。

索引以索引文件的形式存储在磁盘上，当采用 B+Tree 查找的时候，产生磁盘 I/O 消耗对性能的影响比其他方式小很多（ 评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘 I/O 操作次数的渐进复杂度 ）。

换句话说，索引的结构组织要尽量减少查找过程中磁盘 I/O 的存取次数，而 B+Tree 无疑是较优的算法。

原文链接：http://www.cnblogs.com/wzh2010/p/14411428.html

欢迎大家扫码来关注公众号博主，获取文章全部资料，此公众号会持续更新技术干货、不定期分享 Java 进阶面试宝典、Java 核心知识、架构书籍电子版