MySQL数据库系列(六)：MySQL之索引数据结构分析_索引文件数据分析

数据库的索引分类、SQL的优化等在之前文章都有写过。这篇文章单独来说说数据库的原理，也就是说数据库的索引存储结构和为什么这么存储。文章的内容也大多是从其他博客中摘抄下来，并加入自己的理解。

前言

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

数据结构

索引的本质

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

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

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

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

B-Tree

为了描述B-Tree，首先定义一条数据记录为一个二元组[key, data]，key为记录的键值，对于不同数据记录，key是互不相同的；data为数据记录除key外的数据。如图：

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

关于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，例如MySQL就普遍使用B+Tree实现其索引结构。（MySQL数据库中使用的索引名是BTREE，实际上用的就是B+Tree）

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

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

为什么这么做

在BTree(B+tree或者B-Tree)里面，每个节点对应一个存储单元，MySQL中默认一个存储单元的大小是16KB，在主键索引树上，每个存储单元可以存储大约1000对索引值(一个id值和一个指针)，如果以三层来算，前两层都是只存储索引值对，可以存储100万个索引值对。因为第三层需要存储id和对应数据，一个存储单元存储的数据量有限，以正常的一条数据占用空间来算，单个存储单元能存10条数据左右，也就意味着三层树就能存下1000万条数据。这样就使得树的高度不会很高。这样有什么好处呢？

在用id查询的时候，从根节点找到叶子节点，最终找到数据只会经历三个节点。每个节点会在一个存储单元中。也就是只会进行三次IO操作。但是实际是两次，因为根节点是常驻在内存中的，没有读取磁盘的过程。在千万条数据中查找一条数据只会进行两次IO操作，就大大的提高了读取数据的性能。

就算一个数据库中的数据达到亿级，索引树也就只会变为四层，IO读写的次数也就三次，和两次的性能上的差距也不是很大。一般很少有存到亿级数据，达到这个数据后基本都会实行分库分表的。

上面的说法其实很理想，只对主键索引树来说。对于一些普通索引树来说，可能会稍微差一点，但是也不会有太大的出入。（有兴趣的可以算算varhcar(32)或者varchar(64)这些字符串多少层可以达到千万级数据，这里就不一一去算了）

另外还有一点需要强调的是B+Tree的叶子节点是有指针相连的，这样在范围查询的时候即使是跨了叶子节点，效率也会很高。比如要查前20条数据，一个叶子节点上存储10条数据。

• 当有叶子节点之间有指针相连的时候，读到第10条数据，根据指针再继续读下一个叶子节点即可，只会增加一次IO操作。
• 当叶子节点没有指针相连的时候，读到第10条数据，就会断掉，需要根据新的起始边界值从根节点开始向下寻找，直到找到对应的叶子节点，以三层来算，就多了两次IO操作，比上面的方式要多1次IO操作。

这里只涉及到跨两个叶子节点，感觉IO读写次数没有明显的增长，如果涉及到多个呢。这时IO操作次数可就是成倍的增长。

聚集索引和非聚集索引

这里把这个搬出来说，是因为后面说到的内容会涉及到这两个知识点。

非聚集索引

从文件在磁盘上的存储来说，非聚集索引的索引文件和实际的数据文件是两个不同的文件。当在查询数据的时候，是先到索引文件中找到对应的数据存储位置，然后根据这个存储位置到数据文件中查找到对应的实际数据。(可以参考本文的第一张图，把后面的二叉树换成B+Tree就可以了)

聚集索引

聚集索引顾名思义，就是索引内容和实际的数据都存储在同一个文件中。可参考上面的第二和第三张图，数据是直接存储在节点上的。

这两个索引在不同的数据库，不同的存储引擎都有使用到，本文重点要说的MySQL的两个存储引擎MyISAM和InnoDB就使用的到了这两种索引结构。下面就来说说这两种存储引擎是如何使用的。

MyISAM和InnoDB索引结构

从不同的索引树来区分的话，有两种说法，分别是主键索引和辅助索引。主键索引很好理解，除去主键索引，其他的都是辅助索引（好像是一句废话