对数据库索引的一点见解

数据库索引应该是我们平时工作中遇到的和数据库相关问题中比较高频的问题，也是各种面试、晋级答辩中的高频问题。但是大多情况下，我们的回答可能令面试官或答辩评委满意，或者遇到类似的问题往往手足无措，不知道该如何回答，笔者的愿望是希望通过这篇文章，能帮助大家深入的了解下数据库的索引，以后如果遇到类似的问题，我们也可以和人家侃侃而谈。

说到数据库索引是什么，我们可能第一反应都能联想到字典的目录，但是如果我们再想一下，目录是什么？其实目录的本质还是字典的一页，那我们联想一下，那其实索引的本质也是数据。既然索引是数据，那么我们只需要了解它的数据结构和节点存储的数据内容，我们就能想明白索引的很多问题。

要了解索引的数据结构，我们可以设想一下，如果我们自己设计一个索引，我们会怎么实现？在大多数编程语言中，针对文件的操作大多都有一个seek方法，用于从文件的指定位置来读写数据，例如在java中，RandomAccessFile类就提供了这个方法，通过注释我们可以了解到，这个方法为我们提供了从指定位置读写文件。

    /**
     * Sets the file-pointer offset, measured from the beginning of this
     * file, at which the next read or write occurs.  The offset may be
     * set beyond the end of the file. Setting the offset beyond the end
     * of the file does not change the file length.  The file length will
     * change only by writing after the offset has been set beyond the end
     * of the file.
     *
     * @param      pos   the offset position, measured in bytes from the
     *                   beginning of the file, at which to set the file
     *                   pointer.
     * @exception  IOException  if {@code pos} is less than
     *                          {@code 0} or if an I/O error occurs.
     */
    public void seek(long pos) throws IOException

通过这个方法，我们就可以设计一个简单的索引系统，文件A是索引文件，里面保存了id和这条记录在文件B(实际数据文件)中的起始位置。我们可以将索引文件加载到内存中，这样当我们需要查询id为1的数据时，我们就不需要去数据文件B中一行行查找数据，而是可以通过索引文件直接找到id为1的数据文件起始位置0，然后直接通过seek方法定位到指定文件位置，然后直接读取数据即可，这样会大大加快我们查找数据的速度。

简单索引实现

但是当文件大小变得很大的时候，索引文件也会变大，那么检索的速度也会随之减慢，这时候我们应该怎么处理呢？借助分而治之的思想，一个文件过大，我们就把大文件拆分即可。在java语言中，我么可以借助HashMap来实现，最简单的方法就是对id进行取模操作，id为1的数据会被放在一块内存区域中，id为3和13的会放在另外一片内存区域中，这样，我们相当于把一个大文件拆分成了10个文件，忽略取模的事件，我们的查找速度会带来10倍的提升。

HashMap

但是上述方案依然存在一个问题，就是无法提供范围查找的能力，那我们如何设计我们的索引，能提供范围查找的能力呢？这时候我们可能会想到二叉查找树(Binary Search Trees)。二叉查找树规定，对于任何一个子树，这个树的左节点的值都小于根节点，右节的值都大于根节点值。这样当我们进行范围查找时，来到一个节点，如果查找的范围比这个节点小，我们只需要去左树查找即可，如果比这个节点大，我们只需要去右树查找即可。

二叉查找树

但是二叉查找树非常依赖于数据插入的顺序，如果我们按照1->2->3->4....的顺序插入数据是，这时候二叉查找树就会退化成一个链表，这样查找效率又会有所损失。

二叉查找树退化成链表

怎么能避免插入的顺序影响我们查询的效率呢，这个时候我们可能会想到平衡二叉查找树(AVL Trees 【Balanced Binary Search Trees】)，之所以叫AVL树是因为作者名字的首字母缩写是AVL(两位作者，而不是三个哦)。AVL树能够在插入的时候通过左旋和右旋来保证任何一个子树的左树和右树的高度差不超过1，这样的特性保证了我们即使插入的数据是顺序的，AVL树也能自动平衡来达到一个标准的二叉树结构。

AVL树

但是，由于AVL树的特性，要求任何一个树的左树和有树的高度差不能超过1，那么当我们插入数据时，会导致树的频繁左旋和右旋来保证一颗树是一个AVL树，那么，我们插入数据的效率就会变得越来越慢，显然，AVL树也不适合成为一个索引的存储结构。这个时候我们可能会想，如果AVL树的平衡性要求没那严格，是不是就可以成为一个合格的索引结构呢？这个时候我们可能想到红黑树(Red-Black Trees)，红黑树的定义非常繁琐，这里我就不细细描述了，有兴趣的朋友可以自行搜索，红黑树和AVL树最大的区别是红黑树要求任何一个子树的左树和右树的高度差不超过两倍，例如左数的高度是2，那么右树的高度不能超过4，这样特性能保证我们插入数据时避免频繁的左旋和右旋来带来插入性能的损耗。

红黑树

那么红黑树就是索引的最佳数据结构吗？我们可以细细想一想，一个节点我们可以认为是在磁盘的一个数据块，那么这么多树形结构在磁盘中的存储肯定不是顺序存储（因为涉及到树的旋转），那么当我们通过索引查询数据时，需要很多次的随机磁盘读写，我们知道磁盘的随机读写效率都不高，那么这种结构就无法满足我们的快速查找数据的需求。

红黑树的读写效率主要是因为过深的树形结构导致多次随机读写带来的性能损失，那么如果我们将二叉树变成多叉树，是不是就能满足我们的需求呢？这种多叉的树形结构我们称之为B Trees。

B树

那么B树是我们的最佳选择吗？我们来分析下，我们知道计算机读取数据都是按照页读取的，一般的页大小为4K，而数据库一次性读取的数据一般是页的整数倍，如Mysql一次性读取的数据大小为16K。那么我们假设一块磁盘块的大小为16K，单条索引+数据的大小为1K，那么一个磁盘块能放下16个索引，三层的B树能放在的总记录树是16*16*16=4096条，一般超过三层的B树查询速度就无法满足我们的需求，也就是说，B树单表的数据量大概只能在千这个数量级别，而实际我们单表的数据量远远大于这个量，所以说，B树也不是我们最佳的选择。

那么如果我们在B树的非叶子节点不存储数据，只存取索引的值，是不是就能满足我们的需求呢？这种数据结构我们称之为B+ Trees。还是基于上面的假设，我们再次假设索引的大小为百分之一，那么一个磁盘块就可以存储1600条索引信息，那么三层索引能支持的数据量为1600*1600*1600非常非常约等于1000W，这也就是我们所说的关系型数据库能支撑千万级别数据量的原因。所以一般关系型数据库的底层索引存储结构都是B+树。

B+树

搞清楚了索引的数据结构，我们只需要再了解清楚B+树的节点存储的都是什么数据，我们就能彻底了解索引的底层原理。我们知道，索引一般分为主键索引、唯一索引、普通索引和复合索引，下面我们就来一一讨论每种索引的数据的存储方式。

我们知道，主键索引是一个比较特殊的存在，因为数据库的数据是保存在主键索引上的（如果没有主键，会找一个唯一索引，如果还没有唯一索引，那么数据库会生成一个唯一的rowid来绑定），也就是说，主键索引的非叶子节点存储的是主键的索引值，叶子节点存储的就是一行行的数据。这种索引和数据存储在一起的索引我们称之为聚簇索引。

除了主键索引，唯一索引和普通索引非叶子节点存储的还是索引的值，但是他们的叶子节点就无需要在重复存储一份整行的数据，那么它的叶子节点存储的是什么呢？聪明的你应该已经想到了，没错，它的叶子节点的数据存储的就是主键的值。这种索引和数据不存储在一起的我们称之为非聚簇索引。当我们通过这个索引需要查询除了索引的列和主键列以外的列的时候，由于这个索引中的数据不能满足我们的要求，数据库就需要通过主键索引在去主键索引上找到整行数据的其他列，这种行为我们称之为回表。

主键索引

那么复合索引是如何存储的呢？其实复合索引和普通索引一样，非叶子节点存储的也是主键信息，唯一的区别就是索引是按照我们建立的索引列的顺序，把第一列放在前面，第二列紧跟在后面，这个时候我们可以想象成是用一个大的字符串把这几列放在一起拼接成一个大的列，所以我们常说，复合所以的匹配遵循最左匹配，因为如果没有第一列的条件，我们就无法从字符串中的位置进行索引的匹配（跟like条件前面有%的原理是一样的）。

复合索引

这是笔者对数据库索引的一些见解，如果有什么不对的地方，欢迎大家给我留言，一起探讨学习，大家一起进步。