这篇文章的前身是MySQL优化学习手札中的一节，打算系统的讨论一下索引，但是索引也并非依附于MySQL，Elasticsearch中也有倒排索引。于是就将本篇独立了出来，简单的讨论一下索引与查找。
前言
写到这一篇的时候，我想起我的高中时代，那个时候教材总是很多，放在课桌上，上不同的课找不同的书, 一天是八节课，如果你的书架里书排的有序，那找起来比较快，像我这样的惫懒之人一向梳理整理书架，所以基本上一天的课之后，我的书桌都比较乱，这样找书就比较慢，有序的查找起来比无序的查找起来快。
后面到高三的时候，卷子也积累了一批，资料也堆了一批，教材也堆了一堆，他们被放在不同的地方，这个时候脑袋是记得住的，你不需要专门用一张卡片记录一下他们的位置:
但如果你的书籍持续增多呢，你可能需要一个小册了，这个小册记录了书籍详细信息和书籍对应的位置，通常还会按照书籍的首字母进行排序，我记得我高中的图书馆采取的就是这样的方式来快速查找书籍，如果不建立这样的小册，书籍随意的存储，那查找起来就会很慢。这是很朴素的索引思想，这种小册是一种逻辑清单，记录书名和书对应的位置。索引的定义为:
索引是一种线索性指引，它是关键字和相应的物理地址之间的一种逻辑清单。
上面中小册中的书名可以为关键字，物理地址就是在实际的位置。线索性指引，我们可以通过快速查找关键字来找到对应书的位置。
查找的名词解释为:
查找是在数据元素集合中，通过一定的方法找出与给定的关键字相同的数据元素的过程，这个查找的集合对象可以为线性，或者非线性，有序或者无序。经典的查找算法有顺序查找，二分查找及散列查找等技术等。
我们可以说为了快速查找，我们建立索引。通常索引本身是按照关键字有序排列的线性或非线性数据结构。
在MySQL优化系列的视频以及文章中，讲述索引的时候通常将索引看做目录，事实上在使用中它们之间是有明显差别的。日常我们所读的课本前面给出的目录仅仅是按照具体内容的顺序给出，这里的“物理地址”，对图书而言即页码，通常从小到大排列的; 而索引是按照关键字排序，而其对应的”物理地址”不一定有序。当然词典里面的主目录(例如汉语拼音里的拼音索引)常常是以字母为关键字排序的，而碰巧词典的撰写方式都是按照字母顺序编排，因此其主目录就兼具了以拼音为关键字的索引的特点。而汉语词典里面往往还有部首索引，其页面往往是无序的，就具有了索引的典型特征。而普通书本中的目录仅可以视为以章节编号为关键字的索引。
即使是对书本生成的目录和索引，也有类似的区别。目录只是对文献做整体的宏观著录，而索引则可以从不同的角度对文献的某一部分、某一观点或某一知识单元做微观揭示和检索。可见索引的概念比目录本身要广。当然，广义的目录学是涵盖了索引编制的科学。
开始索引历程
线性索引
通常我们组织活动的时候，为了记录谁参加了，我们会准备一个表格，让参加的人填写，我们故事的主人公L先生就是登记参加活动的人，不凑巧的是参加活动的人比较多，落在表格上的人是无序的。这样他找指定的人是否参加活动的时候就比较心酸，需要一页纸一页纸的去找，因为是无序的，只好这样。我们的主人公目前还没有电脑，还不大会用Office、WPS等文字处理软件。L先生又不想重新再将这些数据再按照姓名的首字母再重新排序一次。于是只好自己又做了一个索引表，存取名字和实际的位置，像下面这样:
这个索引表事实上稠密索引，L先生为每一条记录都建立了一个索引项。有的时候，数据本身是有序的，数据量有很多，为每个数据项建立一个索引就没有达到我们快速查找的目的，我们拿到一本英文字典，事实上英文字典的内容就是按照首字母排序的，我们通常会在对应的区域写上对应的字母，这也就是分块索引。
当然如果数据本身的顺序性没有那么强，但是分类却很明确，那么分类就可以做为索引。大家去图书馆找书可能就有类似这样的经验，按照图书的分类可以选择对应的楼层，在对应的楼层再按照这本书的所属的更小的类别再去找这本书在哪些区域，但是如果具体这本书放在第几排第几本就得细细地翻找了。这种情况我们称数据是分段有序的。
综上所说，在为索引顺序文件或者是分段有序的数据表建立索引时，可以降低索引项的数目，采用分块索引的方式。在计算机中，对数据库存取的元素进行查找的时候，一般是先将索引加载到内存中进行检索的，内存是有限的，磁盘上存取的元素不可能都加载进入内存，如果索引项太多，就可能导致频繁在内存与外存之间进行数据交换，影响查找速度。分块存储和索引就是这种情况的最合理解决方案。
分块索引又称稀疏索引，建立一个分块有序的数据表，将n个数据元素“按块有序”划分为m块(m <= n),每一块中的结点不必有序，但块与块之间必须“按块有序”; 即第一块中任一元素的关键字都必须小于第二块任一元素的关键字；而第2块中任一元素的关键字又必须小于第三块的任一元素的关键字......在该分块有序数据表中选取最大关键字构成一个索引表，即为分块索引。由于未对每个记录建立索引项，与稠密索引的概念相对，分块索引也叫稀疏索引。
利用分块索引查找数据的时候，就需要两次查找了，一次是在索引中找到相应的区域，然后在该区域内进行第二次查找。
只要是可以排序的逻辑结构，理论上都可以用于建立索引表, 数据结构中的线性表、树都可以实现排序，因此索引表又可以使用线性数据结构来存储。也可以以树形的方式进行存储。
根据索引是否便于修改，索引又可以分为静态索引和动态索引。根据索引使用的逻辑结构，又可以分为线性索引和树形索引。
根据索引中关键字对应项目在数据表的唯一性，索引中的关键字又可以分为主关键字和次关键字，通常我们所说的索引是指针对主关键字的索引。但一个数据元素往往具有多个特征，这些主关键字之外的特征可以作为次关键字，并且也可以建立相应的索引。
对数据量很大的线性索引仍然比较耗时，还可以在索引表之上建立索引，也就是索引的索引，二级索引，如果数据量仍然很大，仍然可以再建立索引。多级索引会形成类似树形的结构，便于实际中的查找工作。但由于这种索引结构往往以顺序表的方式存储，其索引项不易随着数据项的增减变化而修改。原因在于每次修改或者删除都要对索引表要重新进行一次排序，如果我们在线性表里面建立了多级索引，那么某个元素的更新或者修改就可能要让多级索引重新组织一下。我们将这种类型的索引称之为静态的索引，适用于数据项基本固定的场景。
接下来让我们接着回到L先生上，然而后续L先生还想按照性别和专业分别进行总结进行查找的时候，又不是那么方便了，因为索引表里面目前的主关键字是姓名。于是他又琢磨怎么再用索引的方式让这个记录更好的查阅。然想到的办法是对性别、专业这些信息再各自建立一个索引表，而此时每个索引关键字都对应不止一个记录。也就是这些“关键字”其实是次关键字。在建立次关键字索引时，他就让索引表中的关键字对应的地址是第一条该关键字记录对应的行号；要查找的关键字还存储一个还有谁自己的这个关键字值相同的地址。结果就如下图所示:
多重表示将索引方法和链接方法相结合的一种组织方式。它的具体组织方式是: 对每个需要查询的次关键字建立一个索引，同时将具有相同次关键字的记录链接成一个链表，并将此链表的头指针、链表长度及次关键字，作为索引表的一个索引项。这就是多重表。
在建立多重表之后，L同学发现自己想要找热爱音乐的男同学有几位就比较困难，需要查多个索引表不说，还要在数据表里面翻来翻去，几经周折才能找到自己想要的信息。L同学想到了求交集，L同学灵光一闪想到了一种新的索引方法。这个思路就是在索引表中一次性给出所有相同记录的主关键字值。这样就不用在每条记录里面增加指针条目，得到的结果如下图所示:
这种思路得到的数据表和普通数据表没有什么区别，仅仅是增加了专门用于次关键字的索引表而已，从这两个索引表可以轻松的获知同时具有两个不同条件的同学有几位，而想要找具体的是哪几位，则可以结合主索引表再去查看。这种索引结构叫做倒排表。
倒排表的“倒”或者反向的来历是由于它不是由记录来确定属性值，而是由属性值来确定记录的位置，事实上，现在的主流搜索引擎在处理复杂查询的时候就是基于倒排表来实现，他们可以根据单词快速获取包含这个单词的文档列表。
树形索引
二叉排序树
上面我们讲到线性索引不适合频繁更新的场景，原因在于增加或者删除会需要移动元素。我们也称线性索引为静态索引，那如果说插入的时候能够不移动元素或者插入元素很快呢，这也就是树形索引。让我们从二叉排序树这种数据结构谈起。
二叉排序树(Binary Sort Tree)，又称二叉查找树，也称二叉搜索树，它或者是一颗空树，或者是具有下列性质的二叉树:
(1) 若左子树不空，则左子树上所有结点的值均小于它的根结点的值
(2) 若右子树不空，则右子树上所有结点的值均大于它的根结点的值
(3) 左、右子树也分别为二叉排序树。
在二叉排序树的建立中最关键的操作是插入，而插入是建立在建立查找的基础上的—首先进行查找，若找到该结点的键值则不进行插入，找不到则在最终到达的位置进行插入。查找步骤:
- 若二叉树根结点的关键字值等于查找的关键字, 成功(不可再进行插入)。
- 否则，若小于根结点的关键字值，查左子树。若大于根结点的值查右子树。
- 若子树为空，则插入，表示找到了正确的位置。
二叉排序树不允许键值相同的元素存在。二叉排序树的查询效率在入队元素的不是递增或递减的情况下，如输入为: 50,25,30,60,70的情况下形态如下:
构建过程如下:
(1) 得到50发现程序此时为空树执行插入，50为根结点
(2) 得到25,比50小，查50的左子树，左子树为空，成功插入
(3) 得到60,比50大，查50的右子树，右子树为空，成功插入
(4) 得到30,发现比50小，查50的左子树，跟25比，比25大，放在25的右子树上。
(5) 得到70，发现50大，查50的右子树，也比60大，60的右子树为空，将其放在60的右子树上。
上面的输入序列任意两个元素交换，你会发现最后构建出来的二叉排序树都是不同的，如果我们对二叉树进行中序遍历，就会得到一个从小到达的递增序列，这也是二叉树排序树的一个典型特征：中序深度优先遍历下是有序的！这也是二叉排序树这个名称的由来。
如果上面的输入被构建成了一个线性表，如果不进行排序，那么我们就总是要遍历去查找。而二叉排序树，因为其本身就是有序的，我们就减少的搜索范围。比如我们要查找70，我们只需要比较三次就可以找到。但是在极端情况下，二叉树就会蜕化为链表，比如输入是25,30,50,60,70, 二叉树就蜕化为了链表:
那么有没有办法无论在什么特征的集合上建立二叉排序树，都保证不会出现这样“偏形”的二叉树呢? 相应的策略就是建立平衡二叉树、
平衡二叉树(Banlanced Binary Tree) 又称为AVL树具备以下性质: 它是一颗空树，或它的左右两个子树高度差的绝对值不超过1，并且左右两个子树都是一颗平衡二叉树。构造平衡二叉树的主要思想在于: 如果插入或者删除一个结使得高度之差大于1，就要进行结点之间的旋转，将二叉树重新维持在一个平衡状态。你可以理解为，调整了输入序列一样。但是就算是程序非严格有序，比较良好，没有退化为链表，在数据量比较大的情况下我们也不希望树太高，因为数据量比较大的情况下我们就不可能将磁盘上的元素全部加载进入内存，我们也需要尽量的减少内存和磁盘之间进行数据交换，由此我们就引出了B树，B树的B是Balanced，平衡的意思，也有人将其简单的记为B-树。从字面意思我们可以直到它应该是平衡二叉树的外延概念。
B树简介
采用分块索引和分级索引的方式，在计算机中对数据库数据进行查找，一般是直接将索引项加载到内存进行访问的。如果索引项太多，索引表本身可能因为太大而无法在内存中存储，从而导致频繁在内存与外存(比如硬盘)之间进行数据交换,影响查找速度。B树可以视为一个层级化了的动态分块索引(B树除叶子结点之外的上层索引都是稀疏的)，会指引算法去读取存有想要查找关键字的磁盘上的数据区域，同时可以根据数据的变换灵活的调整树的形态，以保证最少的外存访问次数读取数据。
由于树的深度直接影响了读写外存磁盘的次数多少,因此树的高度越低越好--这时每个结点最多表示一个数据的二叉树就不合时宜了，需要对结点表示数据的个数进行扩展，以降低树的高度。B树就是结点可以有很多孩子，从数个到数千个，它在降低磁盘的I/O操作的数量方面上有明显的优势。
让我们从最简单的非二叉树的B树，2-3树来介绍:
具有下面性质的树称为一颗2-3树:
- 一个结点包含一个或者两个关键字值。
- 每个内部结点有2个子女(如果它包含一个关键字值)，或者3个子女(包含2个关键字值)
- 所有叶子结点在树的同一层，因此树总是高度平衡的；
- 2-3树每一个结点的左子树中所有的后继结点的关键字值都小于其父结点第一个关键字的值；
- 而中间子树所有后继结点的关键字值都大于其父结点第一个关键字的值而小于第二个关键字的值。
- 如果有右子树，则右子树的后继结点的关键字值都大于其父节点第二个关键字的值。
之所以叫2-3树的原因也许是因为每个结点的可能会有两个或三个子女吧。
B树还有很多变种，也在计算机中领域被广泛地应用着。
B+树：在B树的基础上，为叶子结点增加链表指针，而且所有关键字都在也叶子结点出现，非叶子结点仅作为叶子结点的索引。B+树总是到叶子结点才命中，这时非叶子结点就可以看做是对叶子结点而专门设立的索引部分。像下面这样:
术语B树可以指一个特定的方案，也可以指大体上一类方案, 所以B+树在这个意义上可以算做B树，这也是你在MySQL中执行:
show INDEX from 表名;
显示索引类型是BTree而不是B+Tree的原因，但MySQL的索引用的数据结构就是B+Tree，但MySQL的开发人员也许认为BTree是一种解决方案吧。
总结一下
索引技术为查找数据表中的数据而创建一个专用于查找的索引表。每个索引表由多个索引项组成。每个索引项为一个(关键字，地址)的二元组，其中关键字为可以唯一标示数据表中待查结点的数据项。索引表中多个索引项之间一般按照关键字有序排列。为了加快查找速度，我们引入了各种各样的索引，为每一条数据建立的索引，我们称这种索引是稠密索引，如果数据量太大，分类或者这些数据的某一属性比较适合分类，我们可以采用分块索引。单个关键字建立的索引表不符合我们其他维度的查找要求的话，我们针对其他维度再建立索引，也就是多重表。如果查询条件比较复杂，需要两个索引表进行交叉运算，才能快速查找，可以引入倒排表。如果你的数据变化比较多，那么就可以考虑树形索引。
