具体算法8 - 索引的方方面面

本章关键词

索引、查找、需求

索引是软件编写中非常重要的技术，今天这一节我们就回顾一下那些可以用于索引的数据结构，并分析这些数据结构作为索引可以支撑怎样的功能，性能又如何。

为什么需要索引

我粗略地将程序的执行过程分为以下三个步骤：输入-处理-输出。在这三个步骤中，输入和输出对应数据的存储，处理对应计算。

数据的存储要依赖特定的数据结构，不同的数据结构会有不桶的增、删、改、查，的性能。

当存储的数据非常庞大的时候，我们就需要特别关注它们的执行性能了，而影响性能的非常重要的一点，就是索引。索引，通俗地理解，就是在一组数据中寻找到自己需要的数据子集。

索引的需求定义

分析需求，要从功能性需求 和 非功能性需求两个方面来分析，对于索引来说，它们的需求分别如下：

1.功能性需求

数据是格式化数据还是非格式化数据？ 对于非格式化数据，我们一般需要做预处理，提取出查询关键词，对关键词构建索引。

数据是静态数据还是动态数据？ 静态数据通常不涉及频繁的 增、删、改 操作，所以只需要考虑查询效率即可。对于动态数据，我们不仅要考虑查询，也要考虑数据更新带来的索引更新。

索引存储在内存还是硬盘？ 内存的查询速度比硬盘快很多，但是容量有限。硬盘则反之。通常，我们倾向把“小”索引放到内存中，把较“大”的索引放到硬盘中。当然，你可以考虑另一种情况：索引分别存在于两者中。

单值查找还是区间查找？许多时候我们不只是要查找单个数据，还要按范围进行索引。

单关键词查找还是多关键词组合查找？单关键词的查找相对简单，对于多关键词查找，要区分不同的情况。对于结构化的数据，我们可以实现针对多个关键词的组合建立索引（这可能会耗费大量空间）；对于非结构化数据，我们可以分别进行单关键词查找，然后通过集合操作计算出查询结果。

2.非功能性需求

索引对存储空间的消耗不能过大

在考虑查询效率的同时，我们还要考虑索引的维护成本 对动态的数据集合构建的索引，我们需要考虑索引的维护成本，这种维护成本不能过高，否则会影响到数据操作的性能。

构件索引常用的数据结构

在我们学习过的数据结构中，散列表、红黑树、跳表、B+树 等可以作为动态数据的索引。除此之外，位图、布隆过滤器可以作为辅助索引。有序数组也可以用作静态数据的索引

散列表：散列表的增删改查的性能非常好。但是你需要注意装载因子对性能的影响。

红黑树：红黑树是一种常用的平衡二叉查找树，数据的添加、删除、查找的时间复杂度都是O(logn)。

B+ 树 相对于红黑树，B+树 要使用更多的空间构建索引，所以通常我们将它放在硬盘中。为了减轻文件 IO 操作带来的影响，我们会将二叉树改为 m 叉树，以降低树的高度。它支持范围索引

跳表 跳表支持快速添加、删除、查找数据。而且，我们可以灵活调整索引节点的个数和数据个数的比例，平衡内存空间和查询效率的需求。相比于红黑树，它还支持范围索引。

位图和布隆过滤器 这两个数据结构比较节省内存空间，且可以承担一定程度的索引功能，所以我们可以使用它作为辅助索引。例如，布隆过滤器在判定数据不存时不会出错，我们可以利用这个特性加速查询。

有序数组有序数组只能用于静态数据的索引，我们可以使用二分查找快速地定位数据。

各种数据结构的组合学习一定要灵活，基础的数据结构不多，但是我们可以通过组合使用他们实现更多样的功能。例如，使用“散列表 + 有序链表”可以一定程度上实现范围索引。

总结

在这里，我把对于数据结构和索引的思考总结如下：

• 数据的存储，在底层只有两种形式：连续空间存储 和 零散空间存储，这两种形式对应了两种最基本的数据结构：数组 和 链表

• 使用这两种数据结构存储数据的空间利用率是最高的，但是如果想要实现更加快速的查找，我们就需要使用额外的操作，这两种操作是：用额外计算获取数据地址 和 用额外空间保持一种方便查找的结构。

• 用额外的计算获取数据地址，这种思路只能用于数组，因为数组的下标可以计算内存地址。具体应用如下：
  1.使用数组下标进行数据的随机访问，这也是数组的杀手锏
  2.通过对数据的计算确定数据应该存放的位置，这就是散列表，这种计算方法就是哈希函数

• 用额外的空间保持方便查找的结构，这种思路用于“使用零散空间存储数据的情况”，你仔细思考，跳表、红黑树、B+树 是不是都是这种思路的产儿？
  1.跳表通过设置额外的节点索引，实现了加快数据查询的功能。
  2.红黑树、B+树 通过树这种结构用不同孩子保存了不同数据间的关系。

• 不同数据结构的组合可以实现更多功能。

• 如果想实现范围索引，最好的办法是使用有序链表，我们通过某种方法，找到数据范围中的起始结点，然后通过有序链表依次输出范围内的结点，直到数据超出范围，这里有几个现成的例子：
  1.跳表：通过额外的结点找到有序链表的起始结点，然后依次输出
  2.B+树：通过查找叶子节点定位有序链表的起始节点，然后依次输出

---

以上就是关于索引的全部内容，希望能够帮你打开思路

注：本文章的主要内容来自我对极客时间app的《数据结构与算法之美》专栏的总结，我使用了大量的原文、代码和截图，如果想要了解具体内容，可以前往极客时间