MySQL索引结构（B+树、聚簇索引）

参考：http://blog.jobbole.com/24006/

基本定义

MySQL官方对索引的定义为：索引（Index）是帮助MySQL高效获取数据的数据结构.
注意：索引是一种数据结构！

索引的作用——查询

数据库查询是数据库的最主要功能之一。我们都希望查询数据的速度能尽可能的快，因此数据库系统的设计者会从查询算法的角度进行优化。最基本的查询算法当然是顺序查找（linear search），这种复杂度为O(n)的算法在数据量很大时显然是糟糕的，好在计算机科学的发展提供了很多更优秀的查找算法，例如二分查找（binary search）、二叉树查找（binary tree search）等。

但是每种查找算法都只能应用于特定的数据结构之上，例如二分查找要求被检索数据有序。

而索引就是一种数据结构，这种数据结构满足特定查找算法的数据结构，以某种方式引用（指向）数据，这样就可以通过索引实现高级查找算法。

目前大部分数据库系统及文件系统都采用B-Tree或其变种B+Tree作为索引结构，MySQL使用B+Tree实现其索引结构。

索引结构详解

B-Tree有许多变种，其中最常见的是B+Tree，例如MySQL就普遍使用B+Tree实现其索引结构。
与B-Tree相比，B+Tree有以下不同点：

1. 每个节点的指针上限为2d而不是2d+1。
2. 内节点不存储data，只存储key；叶子节点不存储指针。

B-树示意图：

B+树示意图：（注意叶子节点，是只有数据）

MySQL中B+树索引结构，在经典B+Tree的基础上进行了优化，增加了顺序访问指针。

在B+Tree的每个叶子节点增加一个指向相邻叶子节点的指针，就形成了带有顺序访问指针的B+Tree。做这个优化的目的是为了提高区间访问的性能，例如图4中如果要查询key为从18到49的所有数据记录，当找到18后，只需顺着节点和指针顺序遍历就可以一次性访问到所有数据节点，极大提到了区间查询效率。

MySQL索引实例

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

MyISAM索引实现（非聚簇索引）
MyISAM引擎使用B+Tree作为索引结构，叶节点的data域存放的是数据记录的地址（也就是非聚簇索引）。下图是MyISAM索引的原理图：

InnoDB索引实现（聚簇索引）
虽然InnoDB也使用B+Tree作为索引结构，但具体实现方式却与MyISAM截然不同。
第一个重大区别是InnoDB的数据文件本身就是索引文件（也就是聚簇索引）。从上文知道，MyISAM索引文件和数据文件是分离的，索引文件仅保存数据记录的地址。而在InnoDB中，表数据文件本身就是按B+Tree组织的一个索引结构，这棵树的叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键，因此InnoDB表数据文件本身就是主索引。