索引
简介
索引是一个计算机术语，少量数据的检索可以通过轮询进行，但是大量数据的检索需要借助索引进行，索引就是通过提前建好的有序数据指向真正数据的辅助结构。比如我们在一本厚重的字典中如何找到某个汉字，因为字典本身会按照拼音顺序排序，所以你可以直接通过二分的方式查询，但是如果提供一定的索引能力，比如在侧页上印刷上拼音的首字母，仍然会加快我们的索引速度，这就是有序数据的索引方式，引入二级的辅助结构。类似于跳表或者数的中间节点。还有，拼音，部首检字法都是直接定位到汉字的位置，类似于Hash索引。
原理
有序索引
如果数据本身已经是有序的，那么通过二分查找可以快速查询到数据，二分查找的时间复杂度是log(n)。如果n较大的情况下依然会比较慢，使用二分速度仍然可能出现比较次数较多的情况，此时可以借助一个辅助的结构，一般是把数据分段，每段记录起始数据和结束数据，在检索的过程中可以先通过段的索引，然后在段内部进行二分即可。尺寸较厚的词典经常在侧面对不同字母开头的词汇使用一个色块标识，就是减少二分的次数，可以快速定位某个字母开头的词汇。这种方式在消息队列等，LSM树都有应用场景。
有序数据查找的时间复杂度是。
Hash索引
对于无序数据的检索，Hash索引是比较常用的方式，比如常见的缓存，大多采用Hash的方式进行数据检索。Hash是将数据通过一定方式映射为定长的key，然后通过key直接和数据进行关联。
目前流行的 Hash 算法包括 MD5、SHA-1 和 SHA-2等。
| 算法 | 名词解释 |
|---|---|
| FNV | 通过异或和乘法的方式计算Hash，例如乘法的不相关性实现数据的均匀打散。FNV算法可以细分为FNV-0、FNV-1以及FNV-1a |
| Universal Hashing | 定义一组Hash函数表，Hash过程中先从表中随机查找一个Hash算法，之后例如选中的算法进行Hash |
| Zobrist Hashing | 利用棋盘的Hash算法，棋盘不同位置对应不同范围的随机数，然后将不同区域的随机数进行异或操作产生Hash值 |
| MD4 | MD 是 Message Digest 的缩写，输出为 128 位。MD4 目前证明安全性较低。 |
| MD5 | MD4 的改进版本，对输入仍以 512 位分组，其输出是 128 位。MD5计算速度较MD4效率较低，安全性更好。但仍然不能有效抗”强抗碰撞性”。 |
| SHA | 基于MD4算法思想实现的Hash函数族，输出为长度 160 位，常用的SHA算法有SHA-224、SHA-256、SHA-384，和 SHA-512 |
| TigerHash | 例如占位函数和密钥编排（key-schedule）函数交替执行产生的Hash算法。 |
无论何种Hash算法都会产生Hash冲突的问题，通常使用拉链法解决冲突。
B树索引
B-树索引是基于二叉树结构的。B-树索引结构有3个基本组成部分：根节点、分支节点和叶子节点。其中根节点位于索引结构的最顶端，而叶子节点位于索引结构的最底端，中间为分子节点。
- 叶子节点（Leaf node），B树索引中的叶子结点通常是指数据结点。
- 分支节点（Branch node），有指针指向索引里其他分支节点或者叶子节点的节点称为分支节点，分支节点可以有两个指针或者一个指针，左右指针分别指向该节点的左子树和右子树。
- 根节点（Branch node），树的最顶端的节点称为B树索引的根节点。
B-树常见的变种为B+树，B+树的叶子节点之间会有单向链表进行连接。
B+树可以存储的数据量和树的高度，主键长度，以及单条记录的大小有关。
下面用Mysql的InnoDB引擎举例：
Mysql使用页来管理磁盘的数据，默认情况下一页是16K。
对于叶子结点，假如数据库一条记录占用1K的空间，那么一个页面可以存储16条记录。
对于非叶子结点，数据库索引指向下一级节点的指针是6字节，假如数据库索引占用8个字节，那么一个页面可以存储的数据量为16*1024/14=1170条记录。
如果索引的层高为3，则最大存储的数据量是1170*1170*16=21902400条，所以3层B+树大约可以存储2000万条记录。
层高的限制主要和内存有关，3层索引的一个B+树的页面数量是(1+1170+1170*1170)*16K≈1024*1024*16K=16G，如果一个数据库中使用100个索引，索引就会占用1600G内存。因为访问磁盘IO的性能较差，所以数据库需要尽量把索引页面缓存到内存中，缓存1600G数据显然丧失了合理性。
如果是2层B+树，一个索引占用内存是(1+1170)*16K≈16M，即使100张表才占用1.6G的空间，这个空间占用是可以全量缓存的。
数据库的索引访问频率较高，基于内存空间和性能压力，2层索引+1层数据，也就是3层B+树可以实现索引效率（时间复杂度）以及数据量（空间复杂度的均衡）。