提高性能的利器——索引结构基础

写在前面

本篇文章的内容并不是面试常考的八股文（B+树 B+树和XX树的区别 覆盖索引和回表 避免慢查询 等等），而是更教条、更科班的角度从头开始认识索引。同时行文尽量避免“老师上课时知识点罗列一黑板”的风格，尽量做到生动形象、深入浅出。

索引的目的

通过为数据项建立索引，我们可以更快的找到数据项的位置。进一步提高增刪改查的性能，本质上是一种空间换时间的操作。

索引结构基础

一定要有索引吗？

先忽咯你关于 B+树的记忆，先设想一个场景，对于一个数组，判断数组中是否存在一个数，并返回对应的位置。针对这个问题，我们一定要使用索引么？穷举，排序后二分，这些都是比较容易想到的答案。因此我们可以得出结论，通过保证文件有序我们可以大大提高查询的效率。而经典的leveldb便是顺序文件的一个应用。

索引需要记录每个数据项的位置吗？

既然索引是在空间换时间，那我们是否必须存储每个数据项的位置？结合上图，我们也可以看到对于多个顺序文件，我们仅仅需要知道各个文件的上下确界即可。因此索引未必一定要记录所有数据项的位置，这个也就是索引的“稀疏”与“稠密”之分。

先来看下图的稠密索引，这样的索引在什么时候会起到作用呢？无非是花了更多空间的同时，可以更加快速的查询到数据项，两者孰轻孰重，其实是需要具体问题具体分析的。

不过无论是稀疏还是稠密，他们都适用于以下规则：

• 索引条目的大小需要远远小于数据条目的大小，这让我们遍历更加的高效
• 如果索引本身是有序的，我们可以利用二分查找，更加高效的遍历索引
• 当索引文件足够小的时候，我们可以将全部索引放入内存中，彻底的消灭了IO（这也是我们大多数时候使用索引的意义）

当数据量不断增大时，上面的规则就会受到挑战，此时我们可以将稀疏索引和稠密索引融合，多级索引应运而生，他既保证了查询效率的同时，也尽可能的减少了IO次数。这里比较经典的例子就是B+树了。

如果需要针对多个条件查询怎么办？

上面的逻辑仅仅是key -> row 的对应，但很多时候我们会有多个key，我们很难为了不同的key而保留不同排序方式的数据副本及多个索引文件，因此需要使用辅助索引，辅助索引指向的地址是索引本身，这会造成更多的IO，然而这本身也是一种“不得不”的代价。

在顺序文件之外，辅助索引也发挥着他的作用，比如聚集文件结构 不同的文件结构并不是本章讨论的重点，因此读者仅仅需要知道这是将数据项按照某个key值分组存放并且将空间尽量紧凑。那么对于其他key，也不得不使用辅助索引的方式。

key本身不唯一怎么办？

上面举的例子有意忽略一种常见的特殊情况，如果对于一个key，比如class， 多个学生记录里面class字段值都是一样的，如果使用辅助索引的话，就会出现多个同样的索引条目，这会造成键值重复，违背了我们建索引的初衷。

我们通过建立一个叫做桶的间接层来处理这个问题（go语言map的底层实现也是利用了桶，我认为两者有异曲同工之妙）：

bucket_key = 10
point1
point2
point3

我们可以看到，对于索引值为10的桶，里面有指向三条记录的指针，通过桶结构，我们在避免了key的重复写入的同时，也可以迅速得到如下查询的结果

select 
count(1)
from table
where
bucket_key = 10