浅析索引技术
1. 认识索引
索引是一种常见的数据库优化手段，设计优良的索引能够大幅提升数据库的查询效率，提升并发能力。
举一个例子来说，一本《新华字典》收录了日常使用的常见汉字，如果要查其中的一个字，可以采用如下的办法：
- 一页一页的翻，直到找到该字；
- 利用拼音索引，找到这个字对应的页码，根据页码去这一页查看；
- 利用偏旁部首检字法，找到这个字对应的页码，根据页码去这一页查看。
上面三种办法，第一个办法是最慢的，第二和第三种办法，适用于不同的应用场景，如果只知其字不知其音，则偏旁部首检字法较快，如果知道这个字的读音，那么拼音检字法是最快的。
实际上数据库也可以看作是一本收录了所有业务数据的大字典，要检索这本大字典里的数据，可以一个记录一个记录的去遍历查找，也可以编制一个索引，利用索引提升查询效率。
一言以蔽之，索引是为了提高查询的效率出现的。
2. 常见的索引模型及其数据结构
索引的实现方式有很多种，实际上索引也是一种数据的组织方式。就像字典的偏旁部首索引和拼音索引，只是用了不同的方式将字和页码对应了起来。
比较常见的索引模型有下面几种：
- 哈希表
- 有序数组
- 查找树
2.1 哈希表
查找最快的方法是什么？这是一个值得思考的问题，如果有下面一个函数：
value = f(key)
其中key是要找的关键字，value是存储位置，那么我们可以利用这个函数，直接找到key的保存位置，这种方式的时间复杂度是O(1)，基本上找不到比这种方式还快的了。
在《数据结构》这门课程中，这种查找方式被称为散列（hashing）或者哈希。
散列技术是在记录的存储位置和他的关键字之间建立一个确定的对应关系f，使得每个关键字key对应一个存储位置f(key)。对应关系f称为散列函数。
散列既是一种存储方式，也是一种查找方式。
下图展示了一个理想的散列表：
从上图能得出一个结论：
散列技术最适合的是等值查询。
但是散列技术有一个问题，即冲突（collision）问题，问题是这样的，假设存在两个key：key1和key2，其中key1!=key2，但是两个key的散列值却一样，即f(key1)=f(key2)，这样就会出现数据查找错误问题。
为了解决冲突问题，人们提出了多种方案，常见的简单方案有分离链接法和开放定址法。由于本文不是专门描述数据结构和算法的，并不会用很多的篇幅详细描述这两种方法。
下面我们来描述一下分离链接法，其做法是将散列到同一个值的所有元素保留到一个表中。我们一般用链表实现，下面的图展示了这种方法：
这种情况下，f(36)=f(16)=6，在寻找关联字16的时候，搜索到的实际上是一个数组{36,16}，那么此时只需要做一个数组的查找即可得到想要的值。
需要注意的是，我并没有强调散列值是有序的，散列值也不会是有序的，因此如果哈希索引用作范围查找的时候，可能会出现遍历所有散列值的情况，效率非常低下。这一点再次印证了上面的结论：
散列技术最适合的是等值查询。
2.2 表查找
表是最简单的一种ADT，它的定义是零个或者多个数据元素的有限序列。举一个简单的例子，图书馆里书架上的书籍，就可以看作是一个元素为书的表。
表可以有多种实现方式，比如我们可以用数组去实现，也可以用链表来实现。在Java中，对应的也有两种List类型ArrayList和LinkedList。
之前的章节中提到散列技术不适合范围查找，实际上范围查找正是表的长项。
上图是一个顺序表，注意顺序表不是有序表。在这张表上要查询一个元素时，需要从头到尾遍历一遍，最好的情况，时间复杂度是O(1)，最坏的情况，时间复杂度是O(n)，顺序表的平均查找次数为(n+1)/2，因此其时间复杂度仍旧是O(n)。在这样一种数据结构上进行范围查找，显然是不太好的。
但是如果是有序表，情况会变得很不一样：
在这样的一个数据结构上，我们要查找一个元素，对于算法的不二选择就是二分查找。实际上二分查找这个算法虽然简单，但是广泛的应用于数据库系统中。
二分查找的基本思路是：在顺序表中，取中间元素作为比较对象，若给定值和中间记录相等，查找成功；若给定值小于中间元素，则在左半区继续进行二分查找，若给定值大于中间元素，则在右半区继续进行二分查找，直到成功（或失败）为止。
实际上二分查找的算法还包括了递归的思想，这里不再展开。
二分查找的时间复杂度是O(logn)，远远好于顺序查找的O(n)。二分查找是基于有序表的，因此首先还要加一步排序操作，幸运的是数据库在组织索引的时候都是有序的。
如果是范围查找，查找[a, b]区间的数据，只需要首先利用二分查找找到元素a，然后向右遍历表，直到查找到b即可。
这个结构堪称完美，不过还是稍微有一些瑕疵，考虑这样一种情况：超时结账台前的队伍很长，此时一个加塞的人要挤到队伍中，那么如果他成功了，他以后的所有人都要向后挪一位。
表也是如此，一个插入操作或者删除操作都会造成表的元素移动，最好的情况下，这种操作的时间复杂度是O(1)，最坏的情况时间复杂度就会变O(n)，平均时间复杂度还是O(n)。
那么就说明这种数据结构适合元素不怎么变化的情况。当然就不适合数据库的索引了，数据库是用来保存数据的，数据不会一成不变。
2.3 树
树是一种稍微复杂点的数据结构，其大部分操作的时间复杂度都是O(logn)，这种结构很常用，InnoDB的索引就是一棵树的结构。
树是n（n>=0）个节点的有限集合。n=0时称为空树。在任意一颗非空树中，有且仅有一个特定的节点称为根（root）；当n>1时，其余节点可以分为m（m>0）个互不相交的有限集，其中每一个集合又是一棵树，称为根的子树。
上图是一个具体的树的实现。这里说明几个概念：
- 节点的层次：从根开始定义，根的孩子节点为第二层，以此类推；
- 树的深度即树中节点的最大深度。
那么上图中树就是一个深度为3的树。
接下来我们会把一些元素组织称一个二叉查找树，并由此来说明基于二叉查找树的索引。
此时查询一个元素要如何查呢？我们知道二叉查找树的特点是左儿子小于父节点，右儿子大于父节点。那么要找31这个元素，其查找顺序就是：
50-->25-->37-->31
注意上图是一颗平衡二叉树，查找的时间复杂度是O(logn)。
这么看来，一个平衡二叉树，其搜索时间复杂度和有序表一样，那么能否解决有序表添加元素的弊端呢？
下面是一个演示：
对于二叉树来说，这个操作很简单，但是破坏了平衡性，至于如何维持平衡，可以参考专门描述数据结构的书籍。
总体而言，二叉树的搜索效率接近二分查找，且插入效率高于有序表，是一种优良的数据结构。但是数据库系统也没有应用二叉查找树作为索引的数据结构。
其实原因很简单，仍旧如上图所示，不断写入的节点会增加树的深度，那么随着数据的增多，查找的IO消耗就会增加。为了规避这个问题，数据库系统实际上大量采用了B+树。
2.4 B+树
B+树是B树的一种，在本文中，我们会首先介绍B树。B树也叫做多路查找树，实际上B树就是为了磁盘存储出现的一种数据结构。
现代操作系统上有成千上万的系统文件和不计其数的用户文件，这些文件的管理其实也涉及到了数据结构的设计，如果这些文件按照二叉树的样子设计，那么这棵树会变得很大很深，这就会使得读取的次数变得非常多，基于这种效率上的考虑，人们引入了多路查找树。
多路查找树，其每一个节点的孩子树可以多于两个。
B树有很多变种，数据库系统普遍采用的是B+树。接下来的篇幅中会比较详细的叙述B+树。
B树有一个特点，即每个元素只在树上出现一次，但是B+树则不然，所有的元素都会出现在叶子节点上，也有可能出现在分支节点。同时，每个叶子节点都会保存一个指向下一叶子节点的指针。
如果将上面的二叉树转换成一颗B+树，则一定是如下图所示的样子：
只有两层，中间节点所有的元素都会出现在叶子节点中，这实际上已经不再是一颗严格的树了。
如果要搜索37这个元素，只要在[31,56)这个指针的指向地址处进行遍历即可，实际需要遍历的元素只有4个，一般使用二分查找进行遍历，其时间复杂度为O(logn)，对于这个例子，其时间复杂度只有O(1)。
3. 小结
索引技术，实际上一系列数据结构技术的综合应用。虽然现在各项技术，思想层出不穷，但是“数据结构+算法”的经典公式仍旧有意义。
