乐趣区

重新学习Mysql数据库4Mysql索引实现原理

jiezi

MySQL 索引类型

一、简介

MySQL 目前主要有以下几种索引类型：
1. 普通索引
2. 唯一索引
3. 主键索引
4. 组合索引
5. 全文索引

二、语句

<pre>CREATE TABLE table_name[col_name data type]
unique|fulltextindex_name[asc|desc]
</pre>

1.unique|fulltext 为可选参数，分别表示唯一索引、全文索引
2.index 和 key 为同义词，两者作用相同，用来指定创建索引
3.col_name 为需要创建索引的字段列，该列必须从数据表中该定义的多个列中选择
4.index_name 指定索引的名称，为可选参数，如果不指定，默认 col_name 为索引值
5.length 为可选参数，表示索引的长度，只有字符串类型的字段才能指定索引长度
6.asc 或 desc 指定升序或降序的索引值存储

三、索引类型

1. 普通索引
是最基本的索引，它没有任何限制。它有以下几种创建方式：
（1）直接创建索引

<pre>CREATE INDEX index_name ON table(column(length))
</pre>

（2）修改表结构的方式添加索引

<pre>ALTER TABLE table_name ADD INDEX index_name ON (column(length))
</pre>

（3）创建表的时候同时创建索引

<pre>CREATE TABLE table (

`id` int(11) NOT NULL AUTO_INCREMENT ,
`title` char(255) CHARACTER NOT NULL ,
`content` text CHARACTER NULL ,
`time` int(10) NULL DEFAULT NULL ,
PRIMARY KEY (`id`),
INDEX index_name (title(length))

)
</pre>

（4）删除索引

<pre>DROP INDEX index_name ON table
</pre>

2. 唯一索引
与前面的普通索引类似，不同的就是：索引列的值必须唯一，但允许有空值。如果是组合索引，则列值的组合必须唯一。它有以下几种创建方式：
（1）创建唯一索引

<pre>CREATE UNIQUE INDEX indexName ON table(column(length))
</pre>

（2）修改表结构

<pre>ALTER TABLE table_name ADD UNIQUE indexName ON (column(length))
</pre>

（3）创建表的时候直接指定

<pre>CREATE TABLE table (

`id` int(11) NOT NULL AUTO_INCREMENT ,
`title` char(255) CHARACTER NOT NULL ,
`content` text CHARACTER NULL ,
`time` int(10) NULL DEFAULT NULL ,
UNIQUE indexName (title(length))

);
</pre>

3. 主键索引
是一种特殊的唯一索引，一个表只能有一个主键，不允许有空值。一般是在建表的时候同时创建主键索引：

<pre>CREATE TABLE table (

`id` int(11) NOT NULL AUTO_INCREMENT ,
`title` char(255) NOT NULL ,
PRIMARY KEY (`id`)

);
</pre>

4. 组合索引
指多个字段上创建的索引，只有在查询条件中使用了创建索引时的第一个字段，索引才会被使用。使用组合索引时遵循最左前缀集合

<pre>ALTER TABLE table ADD INDEX name_city_age (name,city,age);
</pre>

5. 全文索引
主要用来查找文本中的关键字，而不是直接与索引中的值相比较。fulltext 索引跟其它索引大不相同，它更像是一个搜索引擎，而不是简单的 where 语句的参数匹配。fulltext 索引配合 match against 操作使用，而不是一般的 where 语句加 like。它可以在 create table，alter table，create index 使用，不过目前只有 char、varchar，text 列上可以创建全文索引。值得一提的是，在数据量较大时候，现将数据放入一个没有全局索引的表中，然后再用 CREATE index 创建 fulltext 索引，要比先为一张表建立 fulltext 然后再将数据写入的速度快很多。
（1）创建表的适合添加全文索引

<pre>CREATE TABLE table (

`id` int(11) NOT NULL AUTO_INCREMENT ,
`title` char(255) CHARACTER NOT NULL ,
`content` text CHARACTER NULL ,
`time` int(10) NULL DEFAULT NULL ,
PRIMARY KEY (`id`),
FULLTEXT (content)

);
</pre>

（2）修改表结构添加全文索引

<pre>ALTER TABLE article ADD FULLTEXT index_content(content)
</pre>

（3）直接创建索引

<pre>CREATE FULLTEXT INDEX index_content ON article(content)
</pre>

四、缺点

1. 虽然索引大大提高了查询速度，同时却会降低更新表的速度，如对表进行 insert、update 和 delete。因为更新表时，不仅要保存数据，还要保存一下索引文件。
2. 建立索引会占用磁盘空间的索引文件。一般情况这个问题不太严重，但如果你在一个大表上创建了多种组合索引，索引文件的会增长很快。
索引只是提高效率的一个因素，如果有大数据量的表，就需要花时间研究建立最优秀的索引，或优化查询语句。

五、注意事项

使用索引时，有以下一些技巧和注意事项：
1. 索引不会包含有 null 值的列
只要列中包含有 null 值都将不会被包含在索引中，复合索引中只要有一列含有 null 值，那么这一列对于此复合索引就是无效的。所以我们在数据库设计时不要让字段的默认值为 null。
2. 使用短索引
对串列进行索引，如果可能应该指定一个前缀长度。例如，如果有一个 char(255)的列，如果在前 10 个或 20 个字符内，多数值是惟一的，那么就不要对整个列进行索引。短索引不仅可以提高查询速度而且可以节省磁盘空间和 I / O 操作。
3. 索引列排序
查询只使用一个索引，因此如果 where 子句中已经使用了索引的话，那么 order by 中的列是不会使用索引的。因此数据库默认排序可以符合要求的情况下不要使用排序操作；尽量不要包含多个列的排序，如果需要最好给这些列创建复合索引。
4.like 语句操作
一般情况下不推荐使用 like 操作，如果非使用不可，如何使用也是一个问题。like“%aaa%”不会使用索引而 like“aaa%”可以使用索引。
5. 不要在列上进行运算
这将导致索引失效而进行全表扫描，例如

<pre>SELECT * FROM table_name WHERE YEAR(column_name)<2017;
</pre>

6. 不使用 not in 和 <> 操作

参考 http://blog.codinglabs.org/ar…

摘要

本文以 MySQL 数据库为研究对象，讨论与数据库索引相关的一些话题。特别需要说明的是，MySQL 支持诸多存储引擎，而各种存储引擎对索引的支持也各不相同，因此 MySQL 数据库支持多种索引类型，如 BTree 索引，哈希索引，全文索引等等。为了避免混乱，本文将只关注于 BTree 索引，因为这是平常使用 MySQL 时主要打交道的索引，至于哈希索引和全文索引本文暂不讨论。

文章主要内容分为三个部分。

第一部分主要从数据结构及算法理论层面讨论 MySQL 数据库索引的数理基础。

第二部分结合 MySQL 数据库中 MyISAM 和 InnoDB 数据存储引擎中索引的架构实现讨论聚集索引、非聚集索引及覆盖索引等话题。

第三部分根据上面的理论基础，讨论 MySQL 中高性能使用索引的策略。

数据结构及算法基础

索引的本质

MySQL 官方对索引的定义为：索引（Index）是帮助 MySQL 高效获取数据的数据结构。提取句子主干，就可以得到索引的本质：索引是数据结构。

我们知道，数据库查询是数据库的最主要功能之一。我们都希望查询数据的速度能尽可能的快，因此数据库系统的设计者会从查询算法的角度进行优化。最基本的查询算法当然是顺序查找（linear search），这种复杂度为 O(n)的算法在数据量很大时显然是糟糕的，好在计算机科学的发展提供了很多更优秀的查找算法，例如二分查找（binary search）、二叉树查找（binary tree search）等。如果稍微分析一下会发现，每种查找算法都只能应用于特定的数据结构之上，例如二分查找要求被检索数据有序，而二叉树查找只能应用于二叉查找树上，但是数据本身的组织结构不可能完全满足各种数据结构（例如，理论上不可能同时将两列都按顺序进行组织），所以，在数据之外，数据库系统还维护着满足特定查找算法的数据结构，这些数据结构以某种方式引用（指向）数据，这样就可以在这些数据结构上实现高级查找算法。这种数据结构，就是索引。

看一个例子：

图 1

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

虽然这是一个货真价实的索引，但是实际的数据库系统几乎没有使用二叉查找树或其进化品种红黑树（red-black tree）实现的，原因会在下文介绍。

B-Tree 和 B +Tree

目前大部分数据库系统及文件系统都采用 B -Tree 或其变种 B +Tree 作为索引结构，在本文的下一节会结合存储器原理及计算机存取原理讨论为什么 B -Tree 和 B +Tree 在被如此广泛用于索引，这一节先单纯从数据结构角度描述它们。

B-Tree

为了描述 B -Tree，首先定义一条数据记录为一个二元组[key, data]，key 为记录的键值，对于不同数据记录，key 是互不相同的；data 为数据记录除 key 外的数据。那么 B -Tree 是满足下列条件的数据结构：

d 为大于 1 的一个正整数，称为 B -Tree 的度。

h 为一个正整数，称为 B -Tree 的高度。

每个非叶子节点由 n - 1 个 key 和 n 个指针组成，其中 d <=n<=2d。

每个叶子节点最少包含一个 key 和两个指针，最多包含 2d- 1 个 key 和 2d 个指针，叶节点的指针均为 null。

所有叶节点具有相同的深度，等于树高 h。

key 和指针互相间隔，节点两端是指针。

一个节点中的 key 从左到右非递减排列。

所有节点组成树结构。

每个指针要么为 null，要么指向另外一个节点。

如果某个指针在节点 node 最左边且不为 null，则其指向节点的所有 key 小于 v(key1)v(key1)，其中 v(key1)v(key1)为 node 的第一个 key 的值。

如果某个指针在节点 node 最右边且不为 null，则其指向节点的所有 key 大于 v(keym)v(keym)，其中 v(keym)v(keym)为 node 的最后一个 key 的值。

如果某个指针在节点 node 的左右相邻 key 分别是 keyikeyi 和 keyi+1keyi+ 1 且不为 null，则其指向节点的所有 key 小于 v(keyi+1)v(keyi+1)且大于 v(keyi)v(keyi)。

图 2 是一个 d = 2 的 B -Tree 示意图。

图 2

由于 B -Tree 的特性，在 B -Tree 中按 key 检索数据的算法非常直观：首先从根节点进行二分查找，如果找到则返回对应节点的 data，否则对相应区间的指针指向的节点递归进行查找，直到找到节点或找到 null 指针，前者查找成功，后者查找失败。B-Tree 上查找算法的伪代码如下：

  1. BTree_Search(node, key) {
  2. if(node == null) return null;
  3. foreach(node.key)
  4. {
  5. if(node.key[i] == key) return node.data[i];
  6. if(node.key[i] > key) return BTree_Search(point[i]->node);
  7. }
  8. return BTree_Search(point[i+1]->node);
  9. }
  10. data = BTree_Search(root, my_key);

关于 B -Tree 有一系列有趣的性质，例如一个度为 d 的 B -Tree，设其索引 N 个 key，则其树高 h 的上限为 logd((N+1)/2)logd((N+1)/2)，检索一个 key，其查找节点个数的渐进复杂度为 O(logdN)O(logdN)。从这点可以看出，B-Tree 是一个非常有效率的索引数据结构。

另外，由于插入删除新的数据记录会破坏 B -Tree 的性质，因此在插入删除时，需要对树进行一个分裂、合并、转移等操作以保持 B -Tree 性质，本文不打算完整讨论 B -Tree 这些内容，因为已经有许多资料详细说明了 B -Tree 的数学性质及插入删除算法，有兴趣的朋友可以在本文末的参考文献一栏找到相应的资料进行阅读。

B+Tree

B-Tree 有许多变种，其中最常见的是 B +Tree，例如 MySQL 就普遍使用 B +Tree 实现其索引结构。

与 B -Tree 相比，B+Tree 有以下不同点：

每个节点的指针上限为 2d 而不是 2d+1。

内节点不存储 data，只存储 key；叶子节点不存储指针。

图 3 是一个简单的 B +Tree 示意。

图 3

由于并不是所有节点都具有相同的域，因此 B +Tree 中叶节点和内节点一般大小不同。这点与 B -Tree 不同，虽然 B -Tree 中不同节点存放的 key 和指针可能数量不一致，但是每个节点的域和上限是一致的，所以在实现中 B -Tree 往往对每个节点申请同等大小的空间。

一般来说，B+Tree 比 B -Tree 更适合实现外存储索引结构，具体原因与外存储器原理及计算机存取原理有关，将在下面讨论。

带有顺序访问指针的 B +Tree

一般在数据库系统或文件系统中使用的 B +Tree 结构都在经典 B +Tree 的基础上进行了优化，增加了顺序访问指针。

图 4

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

这一节对 B -Tree 和 B +Tree 进行了一个简单的介绍，下一节结合存储器存取原理介绍为什么目前 B +Tree 是数据库系统实现索引的首选数据结构。

为什么使用 B -Tree（B+Tree）

上文说过，红黑树等数据结构也可以用来实现索引，但是文件系统及数据库系统普遍采用 B -/+Tree 作为索引结构，这一节将结合计算机组成原理相关知识讨论 B -/+Tree 作为索引的理论基础。

一般来说，索引本身也很大，不可能全部存储在内存中，因此索引往往以索引文件的形式存储的磁盘上。这样的话，索引查找过程中就要产生磁盘 I / O 消耗，相对于内存存取，I/ O 存取的消耗要高几个数量级，所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘 I / O 操作次数的渐进复杂度。换句话说，索引的结构组织要尽量减少查找过程中磁盘 I / O 的存取次数。下面先介绍内存和磁盘存取原理，然后再结合这些原理分析 B -/+Tree 作为索引的效率。

B 树

为什么要 B 树

磁盘中有两个机械运动的部分，分别是盘片旋转和磁臂移动。盘片旋转就是我们市面上所提到的多少转每分钟，而磁盘移动则是在盘片旋转到指定位置以后，移动磁臂后开始进行数据的读写。那么这就存在一个定位到磁盘中的块的过程，而定位是磁盘的存取中花费时间比较大的一块，毕竟机械运动花费的时候要远远大于电子运动的时间。当大规模数据存储到磁盘中的时候，显然定位是一个非常花费时间的过程，但是我们可以通过 B 树进行优化，提高磁盘读取时定位的效率。

为什么 B 类树可以进行优化呢？我们可以根据 B 类树的特点，构造一个多阶的 B 类树，然后在尽量多的在结点上存储相关的信息，保证层数尽量的少，以便后面我们可以更快的找到信息，磁盘的 I / O 操作也少一些，而且 B 类树是平衡树，每个结点到叶子结点的高度都是相同，这也保证了每个查询是稳定的。

简介

这里的 B 树，也就是英文中的 B -Tree，一个 m 阶的 B 树满足以下条件：

  1. 每个结点至多拥有 m 棵子树；
  2. 根结点至少拥有两颗子树（存在子树的情况下）；
  3. 除了根结点以外，其余每个分支结点至少拥有 m/2 棵子树；
  4. 所有的叶结点都在同一层上；
  5. 有 k 棵子树的分支结点则存在 k-1 个关键码，关键码按照递增次序进行排列；
  6. 关键字数量需要满足 ceil(m/2)-1 <= n <= m-1；

举个栗子：

B 树上大部分的操作所需要的磁盘存取次数和 B 树的高度是成正比的，在 B 树中可以检查多个子结点，由于在一棵树中检查任意一个结点都需要一次磁盘访问，所以 B 树避免了大量的磁盘访问。

操作

既然是树，那么必不可少的操作就是插入和删除，这也是 B 树和其它数据结构不同的地方，当然了，还有必不可少的搜索，分享一个对 B 树的操作进行可视化的网址，它是由 usfca 提供的。

假定对高度为 h 的 m 阶 B 树进行操作。

插入

新结点一般插在第 h 层，通过搜索找到对应的结点进行插入，那么根据即将插入的结点的数量又分为下面几种情况。

  • 如果该结点的关键字个数没有到达 m - 1 个，那么直接插入即可；
  • 如果该结点的关键字个数已经到达了 m - 1 个，那么根据 B 树的性质显然无法满足，需要将其进行分裂。分裂的规则是该结点分成两半，将中间的关键字进行提升，加入到父亲结点中，但是这又可能存在父亲结点也满员的情况，则不得不向上进行回溯，甚至是要对根结点进行分裂，那么整棵树都加了一层。

其过程如下：

删除

同样的，我们需要先通过搜索找到相应的值，存在则进行删除，需要考虑删除以后的情况，

  • 如果该结点拥有关键字数量仍然满足 B 树性质，则不做任何处理；

  • 如果该结点在删除关键字以后不满足 B 树的性质（关键字没有到达 ceil(m/2)- 1 的数量），则需要向兄弟结点借关键字，这有分为兄弟结点的关键字数量是否足够的情况。

    • 如果兄弟结点的关键字足够借给该结点，则过程为将父亲结点的关键字下移，兄弟结点的关键字上移；
    • 如果兄弟结点的关键字在借出去以后也无法满足情况，即之前兄弟结点的关键字的数量为 ceil(m/2)-1，借的一方的关键字数量为 ceil(m/2)- 2 的情况，那么我们可以将该结点合并到兄弟结点中，合并之后的子结点数量少了一个，则需要将父亲结点的关键字下放，如果父亲结点不满足性质，则向上回溯；
  • 其余情况参照 BST 中的删除。

其过程如下：

B+ 树

为什么要 B + 树

由于 B + 树的数据都存储在叶子结点中，分支结点均为索引，方便扫库，只需要扫一遍叶子结点即可，但是 B 树因为其分支结点同样存储着数据，我们要找到具体的数据，需要进行一次中序遍历按序来扫，所以 B + 树更加适合在区间查询的情况，所以通常 B + 树用于数据库索引，而 B 树则常用于文件索引。

简介

同样的，以一个 m 阶树为例：

  1. 根结点只有一个，分支数量范围为[2，m]；
  2. 分支结点，每个结点包含分支数范围为[ceil(m/2), m]；
  3. 分支结点的关键字数量等于其子分支的数量减一，关键字的数量范围为[ceil(m/2)-1, m-1]，关键字顺序递增；
  4. 所有叶子结点都在同一层；

操作

其操作和 B 树的操作是类似的，不过需要注意的是，在增加值的时候，如果存在满员的情况，将选择结点中的值作为新的索引，还有在删除值的时候，索引中的关键字并不会删除，也不会存在父亲结点的关键字下沉的情况，因为那只是索引。

B 树和 B + 树的区别

这都是由于 B + 树和 B 具有这不同的存储结构所造成的区别，以一个 m 阶树为例。

  1. 关键字的数量不同；B+ 树中分支结点有 m 个关键字，其叶子结点也有 m 个，其关键字只是起到了一个索引的作用，但是 B 树虽然也有 m 个子结点，但是其只拥有 m - 1 个关键字。
  2. 存储的位置不同；B+ 树中的数据都存储在叶子结点上，也就是其所有叶子结点的数据组合起来就是完整的数据，但是 B 树的数据存储在每一个结点中，并不仅仅存储在叶子结点上。
  3. 分支结点的构造不同；B+ 树的分支结点仅仅存储着关键字信息和儿子的指针（这里的指针指的是磁盘块的偏移量），也就是说内部结点仅仅包含着索引信息。
  4. 查询不同；B 树在找到具体的数值以后，则结束，而 B + 树则需要通过索引找到叶子结点中的数据才结束，也就是说 B + 树的搜索过程中走了一条从根结点到叶子结点的路径。

主存存取原理

目前计算机使用的主存基本都是随机读写存储器（RAM），现代 RAM 的结构和存取原理比较复杂，这里本文抛却具体差别，抽象出一个十分简单的存取模型来说明 RAM 的工作原理。

图 5

从抽象角度看，主存是一系列的存储单元组成的矩阵，每个存储单元存储固定大小的数据。每个存储单元有唯一的地址，现代主存的编址规则比较复杂，这里将其简化成一个二维地址：通过一个行地址和一个列地址可以唯一定位到一个存储单元。图 5 展示了一个 4 x 4 的主存模型。

主存的存取过程如下：

当系统需要读取主存时，则将地址信号放到地址总线上传给主存，主存读到地址信号后，解析信号并定位到指定存储单元，然后将此存储单元数据放到数据总线上，供其它部件读取。

写主存的过程类似，系统将要写入单元地址和数据分别放在地址总线和数据总线上，主存读取两个总线的内容，做相应的写操作。

这里可以看出，主存存取的时间仅与存取次数呈线性关系，因为不存在机械操作，两次存取的数据的“距离”不会对时间有任何影响，例如，先取 A0 再取 A1 和先取 A0 再取 D3 的时间消耗是一样的。

磁盘存取原理

上文说过，索引一般以文件形式存储在磁盘上，索引检索需要磁盘 I / O 操作。与主存不同，磁盘 I / O 存在机械运动耗费，因此磁盘 I / O 的时间消耗是巨大的。

图 6 是磁盘的整体结构示意图。

图 6

一个磁盘由大小相同且同轴的圆形盘片组成，磁盘可以转动（各个磁盘必须同步转动）。在磁盘的一侧有磁头支架，磁头支架固定了一组磁头，每个磁头负责存取一个磁盘的内容。磁头不能转动，但是可以沿磁盘半径方向运动（实际是斜切向运动），每个磁头同一时刻也必须是同轴的，即从正上方向下看，所有磁头任何时候都是重叠的（不过目前已经有多磁头独立技术，可不受此限制）。

图 7 是磁盘结构的示意图。

图 7

盘片被划分成一系列同心环，圆心是盘片中心，每个同心环叫做一个磁道，所有半径相同的磁道组成一个柱面。磁道被沿半径线划分成一个个小的段，每个段叫做一个扇区，每个扇区是磁盘的最小存储单元。为了简单起见，我们下面假设磁盘只有一个盘片和一个磁头。

当需要从磁盘读取数据时，系统会将数据逻辑地址传给磁盘，磁盘的控制电路按照寻址逻辑将逻辑地址翻译成物理地址，即确定要读的数据在哪个磁道，哪个扇区。为了读取这个扇区的数据，需要将磁头放到这个扇区上方，为了实现这一点，磁头需要移动对准相应磁道，这个过程叫做寻道，所耗费时间叫做寻道时间，然后磁盘旋转将目标扇区旋转到磁头下，这个过程耗费的时间叫做旋转时间。

局部性原理与磁盘预读

由于存储介质的特性，磁盘本身存取就比主存慢很多，再加上机械运动耗费，磁盘的存取速度往往是主存的几百分分之一，因此为了提高效率，要尽量减少磁盘 I /O。为了达到这个目的，磁盘往往不是严格按需读取，而是每次都会预读，即使只需要一个字节，磁盘也会从这个位置开始，顺序向后读取一定长度的数据放入内存。这样做的理论依据是计算机科学中著名的局部性原理：

当一个数据被用到时，其附近的数据也通常会马上被使用。

程序运行期间所需要的数据通常比较集中。

由于磁盘顺序读取的效率很高（不需要寻道时间，只需很少的旋转时间），因此对于具有局部性的程序来说，预读可以提高 I / O 效率。

预读的长度一般为页（page）的整倍数。页是计算机管理存储器的逻辑块，硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块，每个存储块称为一页（在许多操作系统中，页得大小通常为 4k），主存和磁盘以页为单位交换数据。当程序要读取的数据不在主存中时，会触发一个缺页异常，此时系统会向磁盘发出读盘信号，磁盘会找到数据的起始位置并向后连续读取一页或几页载入内存中，然后异常返回，程序继续运行。

B-/+Tree 索引的性能分析

到这里终于可以分析 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)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))dmax=floor(pagesize/(keysize+datasize+pointsize))

floor 表示向下取整。由于 B +Tree 内节点去掉了 data 域，因此可以拥有更大的出度，拥有更好的性能。

这一章从理论角度讨论了与索引相关的数据结构与算法问题，下一章将讨论 B +Tree 是如何具体实现为 MySQL 中索引，同时将结合 MyISAM 和 InnDB 存储引擎介绍非聚集索引和聚集索引两种不同的索引实现形式。

MySQL 索引实现

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

MyISAM 索引实现

MyISAM 引擎使用 B +Tree 作为索引结构，叶节点的 data 域存放的是数据记录的地址。下图是 MyISAM 索引的原理图：

图 8

这里设表一共有三列，假设我们以 Col1 为主键，则图 8 是一个 MyISAM 表的主索引（Primary key）示意。可以看出 MyISAM 的索引文件仅仅保存数据记录的地址。在 MyISAM 中，主索引和辅助索引（Secondary key）在结构上没有任何区别，只是主索引要求 key 是唯一的，而辅助索引的 key 可以重复。如果我们在 Col2 上建立一个辅助索引，则此索引的结构如下图所示：

图 9

同样也是一颗 B +Tree，data 域保存数据记录的地址。因此，MyISAM 中索引检索的算法为首先按照 B +Tree 搜索算法搜索索引，如果指定的 Key 存在，则取出其 data 域的值，然后以 data 域的值为地址，读取相应数据记录。

MyISAM 的索引方式也叫做“非聚集”的，之所以这么称呼是为了与 InnoDB 的聚集索引区分。

InnoDB 索引实现

虽然 InnoDB 也使用 B +Tree 作为索引结构，但具体实现方式却与 MyISAM 截然不同。

第一个重大区别是 InnoDB 的数据文件本身就是索引文件。从上文知道，MyISAM 索引文件和数据文件是分离的，索引文件仅保存数据记录的地址。而在 InnoDB 中，表数据文件本身就是按 B +Tree 组织的一个索引结构，这棵树的叶节点 data 域保存了完整的数据记录。这个索引的 key 是数据表的主键，因此 InnoDB 表数据文件本身就是主索引。

图 10

图 10 是 InnoDB 主索引（同时也是数据文件）的示意图，可以看到叶节点包含了完整的数据记录。这种索引叫做聚集索引。因为 InnoDB 的数据文件本身要按主键聚集，所以 InnoDB 要求表必须有主键（MyISAM 可以没有），如果没有显式指定，则 MySQL 系统会自动选择一个可以唯一标识数据记录的列作为主键，如果不存在这种列，则 MySQL 自动为 InnoDB 表生成一个隐含字段作为主键，这个字段长度为 6 个字节，类型为长整形。

第二个与 MyISAM 索引的不同是 InnoDB 的辅助索引 data 域存储相应记录主键的值而不是地址。换句话说，InnoDB 的所有辅助索引都引用主键作为 data 域。例如，图 11 为定义在 Col3 上的一个辅助索引：

图 11

这里以英文字符的 ASCII 码作为比较准则。聚集索引这种实现方式使得按主键的搜索十分高效，但是辅助索引搜索需要检索两遍索引：首先检索辅助索引获得主键，然后用主键到主索引中检索获得记录。

了解不同存储引擎的索引实现方式对于正确使用和优化索引都非常有帮助，例如知道了 InnoDB 的索引实现后，就很容易明白为什么不建议使用过长的字段作为主键，因为所有辅助索引都引用主索引，过长的主索引会令辅助索引变得过大。再例如，用非单调的字段作为主键在 InnoDB 中不是个好主意，因为 InnoDB 数据文件本身是一颗 B +Tree，非单调的主键会造成在插入新记录时数据文件为了维持 B +Tree 的特性而频繁的分裂调整，十分低效，而使用自增字段作为主键则是一个很好的选择。

下一章将具体讨论这些与索引有关的优化策略。

两种引擎索引的比较：

B-/+Tree 索引的性能优势：一般使用磁盘 I / O 次数评价索引优劣。

1. 结合操作系统存储结构优化处理：mysql 巧妙运用操作系统存储结构(一个节点分配到一个存储页中 -> 尽量减少 IO 次数) & 磁盘预读(缓存预读 -> 加速预读马上要用到的数据).

2.B+Tree 单个节点能放多个子节点，相同 IO 次数，检索出更多信息。

3.B+TREE 只在叶子节点存储数据 & 所有叶子结点包含一个链指针 & 其他内层非叶子节点只存储索引数据。只利用索引快速定位数据索引范围，先定位索引再通过索引高效快速定位数据。

详解：Mysql 设计利用了磁盘预读原理，将一个 B +Tree 节点大小设为一个页大小，在新建节点时直接申请一个页的空间，这样就能保证一个节点物理上存储在一个页里，加之计算机存储分配都是按页对齐的，这样就实现了每个 Node 节点只需要一次 I / O 操作。

B-Tree 索引、B+Tree 索引：单个节点能放多个子节点，查询 IO 次数相同(mysql 查询 IO 次数最多 3 - 5 次 - 所以需要每个节点需要存储很多数据)

B+TREE 只在叶子节点存储数据 & 所有叶子结点包含一个链指针 & 其他内层非叶子节点只存储索引数据。只利用索引快速定位数据索引范围，先定位索引再通过索引高效快速定位数据。

B+Tree 更适合外存索引，原因和内节点出度 d 有关。从上面分析可以看到，d 越大索引的性能越好，而出度的上限取决于节点内 key 和 data 的大小：

B+Tree 内节点去掉了 data 域，因此可以拥有更大的出度，拥有更好的性能。只利用索引快速定位数据索引范围，先定位索引再通过索引高效快速定位数据。

dmax=floor(pagesize/(keysize+datasize+pointsize))

Mysql 索引底层实现 -MyISAM & InnoDB

聚簇索引：索引 和 数据文件为同一个文件。非聚簇索引：索引 和 数据文件分开的索引。

MyISAM & InnoDB 都使用 B +Tree 索引结构。但是底层索引存储不同，MyISAM 采用非聚簇索引，而 InnoDB 采用聚簇索引。

MyISAM 索引原理：采用非聚簇索引 -MyISAM myi 索引文件和 myd 数据文件分离，索引文件仅保存数据记录的指针地址。叶子节点 data 域存储指向数据记录的指针地址。(底层存储结构：frm - 表定义、myi -myisam 索引、myd-myisam 数据)

MyISAM 索引按照 B +Tree 搜索，如果指定的 Key 存在，则取出其 data 域的值，然后以 data 域值 - 数据指针地址去读取相应数据记录。辅助索引和主索引在结构上没有任何区别，只是主索引要求 key 是唯一的，而辅助索引的 key 可以重复。MyISAM 索引树如下：

InnoDB 优势：高扩展性，充分发挥硬件性能、Crash Safe、支持事务、可以在线热备份

InnoDB 特性：

1. 事务支持（ACID）2. 扩展性优良 3. 读写不冲突 4. 缓存加速

2. 功能组件: redo/undo &  异步 IO &  MVCC & 行级别锁 & Page Cache（LRU）

InnoDB 物理存储结构如下图：

InnoDB 表空间管理

InnoDB 物理存储文件结构说明：

    InnoDB 以表空间 Tablespace(idb 文件)结构进行组织，每个 Tablespace 包含多个 Segment 段，每个段(分为 2 种段：叶子节点 Segment& 非叶子节点 Segment), 一个 Segment 段包含多个 Extent，一个 Extent 占用 1M 空间包含 64 个 Page（每个 Page 16k），InnoDB B-Tree 一个逻辑节点就分配一个物理 Page, 一个节点一次 IO 操作。, 一个 Page 里包含很多有序数据 Row 行数据，Row 行数据中包含 Filed 属性数据等信息。

• 表空间(ibd 文件)

• 段(一个索引 2 段：叶子节点 Segment & 非叶子节点 Segment）

• Extent（1MB）：一个 Extent(1M) 包含 64 个 Page(16k), 一个 Page 里包含很多有序行数据 , InnoDB B-Tree 一个逻辑节点就分配一个物理 Page, 一个节点一次 IO 操作。

• Page(16KB)

• Row

• Field

表插入数据扩展原理：一次扩张一个 Extent 空间（1M），64 个 Page, 按照顺序结构向每个 page 中插入顺序。

InnoDB 逻辑组织结构：

InnoDB 索引树结构

每个索引一个 B + 树，一个 B + 树节点 = 一个物理 Page（16K）

• 数据按 16KB 切片为 Page 并编号，编号可映射到物理文件偏移(16K * N），B+ 树叶子节点前后形成双向链表，数据按主键索引聚簇，二级索引叶节点存储主键值，通过叶节点主键值回表查找数据。

InnoDB 索引原理：

  采用聚簇索引 - InnoDB 数据 & 索引文件为一个 idb 文件，表数据文件本身就是主索引，相邻的索引临近存储。叶节点 data 域保存了完整的数据记录(数据[除主键 id 外其他列 data]+ 主索引[索引 key: 表主键 id])。叶子节点直接存储数据记录，以主键 id 为 key, 叶子节点中直接存储数据记录。(底层存储结构: frm - 表定义、ibd: innoDB 数据 & 索引文件)

注：由于 InnoDB 采用聚簇索引结构存储，索引 InnoDB 的数据文件需要按照主键聚集，因此 InnoDB 要求表必须有主键 (MyISAM 可以没有)。如果没有指定 mysql 会自动选择一个可以唯一表示数据记录的列作为主键，如果不存在这样的列，mysql 自动为 InnoDB 表生成一个隐含字段(6 个字节长整型) 作为主键。InnoDB 的所有 辅助索引 都引用 数据记录的主键 作为 data 域。

  聚簇索引这种实现方式使得按主键的搜索十分高效，但是辅助索引搜索需要检索两遍索引：首先检索辅助索引获得数据记录主键，然后用主键到主索引中检索获得数据记录。InnoDB 聚簇索引结构：

索引查找流程：

1. 索引精确查找: 确定定位条件, 找到根节点 Page No, 根节点读到内存, 逐层向下查找, 读取叶子节点 Page, 通过 二分查找找到记录或未命中。（select * from user_info where id = 23）

2. 索引范围查找：读取根节点至内存, 确定索引定位条件 id=18, 找到满足条件第一个叶节点

, 顺序扫描所有结果, 直到终止条件满足 id >=22（select * from user_info where id >= 18 and id < 22）

3. 全表扫描：直接读取叶节点头结点，顺序扫描，返回符合条件记录，到最终节点结束

（select * from user_info where name = ‘abc’）

4. 二级索引查找

Create table table_x(int id primary key, varchar(64) name,key sec_index(name) )

• Select * from table_x where name =“d”;

通过二级索引查出对应主键，拿主键回表查主键索引得到数据，二级索引可筛选掉大量无效记录，提高效率

退出移动版