漫谈数据库索引

为什么要了解数据索引呢？我们都知道索引结构一般会加速查询，那这些索引是如何加速查询的呢？我们有时候建立了索引，但是查询比没建索引都要慢，这又是为什么呢？我们有时候会根据不同的业务场景选择不同的索引类型，选择的依据又是什么呢？

带着以上几个疑惑，让我们开始了解数据库索引到底是啥，它的底层数据结构是什么样子的，是怎样加速查询的，索引本身又做了哪些优化。希望读完本文后，可以为你解决上述存留在心中的疑问。

在这里也顺便提下个人对大数据的理解，大数据其实就是海量数据的存储和检索，前者关注于如何更高效的把数据放到存储介质上，后者关注于如何更高效的把数据从存储介质上检索出来，需要注意这里的检索指的是检查数据是否存在，如果数据存在则返回。而索引又是检索的核心，了解索引之后会对理解整个检索过程有更深刻的理解，比如执行计划的解析，join order 等等的影响。

数组和链表

数据和链表作为最基础的数据结构，往往也是被容易忽视的。但是却又非常重要，可以说我们接触的大部分索引结构都是由数组和链表结合而成的，比如位图本身就是以 bit 为单位的数据，再比如二叉查找树，红黑树，调表本身就是每个节点带多个指针的链表，再比如更高阶的 B+ 树，就是一个多叉树（带多个指针的链表），其每个节点又是一个数组，每层节点之间又会互相引用形成双向链表，再比如…….。

可以看到就算在复杂的数据结构，其基本单元依然是数组和链表，只有了解数组和链表本身的特性以及查询原理才能更深入了解高阶的数据结构是如何加速查询的，以及如何从低阶数据结构转向高阶数据结构。

首先看下数组，你认为的数组是什么呢，是存放元素的容器还是仅仅简单的列表。都不是，数组只是开辟在内存区域上的一块连续空间，有时候甚至不是物理连续的，但是一定具有逻辑连续性。因为在内存上具有连续性，所以数组具有随机访问的特性，并且由于内存局部性原理，在小数据量下具有更高的查询性能。

tips：一般加载运行程序都是从外设中加载到内存，然后 cpu 在从内存中取出相应数据放到寄存器中，而现代 pc 一般都会有多层寄存器缓存，为了加速 cpu 运算，一般会把相邻内存空间区域下的数据也加载放入到缓存中。这样的话，下次则不需要再访问这些内存空间中的数据，而是直接加载 cpu 缓存即可。而数组正是应用了这个原理来实现的查询加速。

数组在有序情况下，因为随机访问的特性，可以方便的利用二分查找来定位数据，这也是为何绝大多数查询，计算引擎（比如 mapreduce）为啥会有默认分区排序的原因。

既然数组已经这么好了，为啥还需要链表呢？让我们思考这样的场景，数组放不下了该怎么办，答案是需要重新开辟空间，复制数据。再数据高频写入场景下，采用数组来存放数据显然不行，重新申请内存的开销太大。还有有序数据插入删除数据的时候，更不适合。这时候就需要链表出场了，链表通过指针的方式来连接每个元素，当需要插入删除时只需要修改对应节点的前后两个指针即可，极大的降低了增删改查的开销。但是链表的问题也随之而来，因为每个节点只能通过前置指针去访问，失去了随机访问的能力，即使在链表有序的情况下，也无法做到二分查找。

好了，我们现在总结一下。

数组随机访问，范围查询，基于内存的局部性原理在小数据规模下具有更良好的检索性能，但是插入删除开销比较大，尤其是在有序数组情况下。
链表增删方便，但是失去了随机访问能力，即使数据有序情况下，也无法提高检索性能。

我们自己也可以思考下该如何改造链表使得其具有二分查找的能力呢？

二叉查找树（BST → RBT & 跳表）

基于上一节中的留给我们的问题，对链表进行了改造。也就是我们常说的 BST（二叉查找树），那到底是如何改造的呢。想想数组的二分查找是如何做的呢，先找到中间节点，在折半数组中接着找中间节点，直到定位到目标值或者遍历完为止。那链表该如何快速定位到中间节点呢，一个办法是每个节点除了指向下一个节点的指针，在额外增加一个指向中间节点的指针，那到了中间节点指针之后，还需要知道中间节点左右两边的中间节点指针（ps：此处有点绕口），那么中间节点也需要有前向指针。好了，到此处，我们应该明白了，为链表每个节点设置两个指针，左指针元素小于 < 中间节点 < 右指针元素。emmm，这样一个可以二分查找的有序链表就出来了，可以看到 BST 本身就是链表。

通过上述链表改造，链表也可以二分查找了，具有更高效的检索能力了。但是所有情况下，BST 一定比普通链表查找快吗？非也，BST 在倾斜的情况下会退化成链表，所以为了解决倾斜问题，又衍生出来非常多的数据结构，比如红黑树（RBT），跳表，AVL 等。实际上就是在增删过程中应用一些规则尽可能的保持 BST 的平衡性。

这里可以说下红黑树和跳表。

红黑树大家应该相对熟悉，java 的 hashmap 就是数组+红黑树实现的，加入红黑树是为了解决大量哈希冲突下元素的检索性能。

跳表和红黑树解决平衡性问题的思路就大相径庭了，不过熟悉 es，redis 中的人应该知道，比如 es 的倒排索引就是用跳表来加速检索的。跳表可以理解为对普通链表加上了高速缓存，即每个节点存在有多个指针指向后续节点（每个节点的指针个数称之为层数，层数会通过概率函数随机生成，这也是为了保证跳表的指针分布更加均匀）。在大数据规模下，跳表的实现相对于红黑树这些更加简单，且也能实现 O(logn) 的检索性能。

这里在提个问题，跳表的增删节点怎么处理呢，毕竟每个节点都有可能指向同一个指针，难道需要全部指针都需要处理吗？

哈希表来了，我们想起 O(1) 时间复杂度的数据结构，第一个想起的总会是哈希表。那么哈希表是如何做到 O(1) 时间复杂度的呢。哈希表顾明思议是先哈希后落表。针对 int 类型的数据，我们可以开辟一个数组，int 是啥就在数据的哪个位置上放置该元素，当查询时，只需要通过数据的随机访问能力就可以快速查询到对应值以及对应值是否存在。针对 string 类型的数据，我们可以做编码处理转换成 int 值（这个过程也叫散列），举个例子，Tom，我们就可以按照 26 个字母的顺序进行编码，类似于二进制计算的方式将一个字符串转换为数值类型。当然散列函数的方法是多种多样的，这里就不过多赘述了。

好了，现在我们已经明确哈希表就是数组实现的了。但是数组也是有限制的，不可能无限开辟连续内存的空间，因此一定会碰到哈希冲突。哈希冲突又有哪几种解决办法呢？开放寻址和链表法。

开放寻址法，在碰到哈希冲突后，继续向后移寻找位置，容易造成位置抢占。或者通过多个 hash 函数来处理。
链表法，在碰到哈希冲突后，直接将冲突元素加到冲突节点上，形成链表。缺点是哈希冲突过多后，o(1) 的时间复杂度会退化成 o(n)，因为需要遍历链表。因此有些 hashmap 的实现会将链表达到一定规模后再进化成红黑树。

哈希表具有 O(1) 的时间复杂度，看起来很美好，但是本质上是无序数组，失去了遍历能力，并且为了避免频繁的哈希冲突，一般还会预留额外空间（可以了解下装载因子），rehash 的代价也是比较大的。

从上我们也可以看出，hash 表适合用于检测数据存在的场景，这点和布隆过滤器类似，只不过布隆过滤器的压缩比更好。此处也可以联想到 hashshuffle 和 hashjoin，都是采用的这种结构。

问题又来了，哈希表的删除操作在开放寻址法和链表法下有啥不同呢？

布隆过滤器

有了哈希表的 o(1)，为何还需要布隆过滤器。在大规模数据量下，哈希表所占用的内存空间极大，比如向一些基于 lsm 的引擎，比如 doris，druid ，kafka 这些，往往需要预判数据，如果采用哈希表做预判的话则会占用大量内存空间。那么布隆过滤器是如何做压缩的呢？

一个数据结构的大小可以用（数据大小 * 数据个数） 来表达，布隆过滤器做的第一个优化就是该表数据大小，以 bit 为单位进行处理，因为往往我们做预判只是需要是否的概念，用0 和 1 就可以表达。第二个优化就是减少数据个数，利用 k 个哈希函数来对 k 个位置进行 bit 位赋值，这里的 k 的个数也是有一套算法在里面的。通过这样的方式极大大压缩了数据结构的大小。

选用 k 个哈希函数也带了一定预判误差率，因为有可能一个没有的元素的 k 个位置都被置为了 1 bit。

布隆过滤器常用于预判场景（在基于 lsm 引擎的 olap 中尤为常见），并且适合于高基维字段，这里可以自己思考下为什么适用于高基维呢？

倒排索引是啥？我们可以先想下正排索引是什么？举个例子类比，通过诗歌名找到诗歌是正排索引，通过诗歌内容找到包含所有该内容的诗歌名称是倒排索引。倒排索引是如何构建的。

倒排索引常用于搜索引擎，比如 mysql 中的全文搜索，es 中的检索，都有倒排索引的出现。

B+树 vs LSM

上面我们了解的很多数据结构，也可以说是索引都是放在内存中的（这里不严谨，也是可以落到磁盘的）。那么在大规模索引情况下，索引该如何下方到磁盘中，我们又该如何访问磁盘中的数据索引呢？B+ 树和 LSM 就是索引落盘的经典实现

一些实际问题

万丈高楼皆起于平地之间，技术如此，我们亦如此。