1. 索引是什么？
索引这个概念就好比书的目录，要查找的数据就是某个知识点。如果没有目录，那么我们要去查找某个知识点的时候，就要一页一页的翻。但是，有了目录之后，我们通过目录即可定位到相关知识点的页数，从而提高查找的速度。同理，索引的作用也是如此。
2. 为什么需要索引？
在实际的软件开发中，功能千遍万换，但是本质都是“对数据的存储和计算”，对应到数据结构中，“存储”就是数据结构，“计算”就是算法。
对于存储来说，功能上无外乎是“增删改查”这四种操作。这四种操作其实并不复杂，但是一旦存储的数据变多了，那么性能也就会受到影响，因此性能就成了这些系统要关注的重点了。比如在一些跟存储相关的基础系统（MySQL、分布式文件系统）、中间件（消息中间件 RocketMQ）中，关注的重点有一个就是性能。那么在存储的改进上，提升增删改查执行效率的一个方式就是增加索引。但是，索引设计得好坏，也会决定这些系统的性能。
3. 怎么设计索引呢？
在设计索引之前，我们需要考虑具体的一个场景，也就是定义清楚需求到底是什么？对于系统设计来说，需求分析一般从功能性和非功能性两方面来分析。
3.1. 需求
功能性需求
- 数据是格式化数据还是非格式化数据。对于要构建索引的原始数据，我们将其划分为两类，一类是结构化数据，比如 MySQL 中的数据，另一类是非结构化的数据，比如搜索引擎。对于非结构化数据，我们一般要做预处理，提取出查询关键词，对提取出来的关键词构建索引。
- 数据是静态数据还是动态数据。假如原始数据是一组静态数据，不会有数据的增、删、更新操作，那么在构建索引的时候，我们只需要考虑查询即可。假如原始数据是一组动态数据，那么我们不仅需要考虑到索引的查询效率，还要考虑到数据更新时的效率。
- 索引存储在内存还是硬盘。（PS：这点让我想起了 B+ 树的索引，它就是存储在硬盘中的）索引存储在内存中的话，查询的速度肯定要比存储在磁盘中的要高。但是，在原始数据量很大的情况下，对应的索引可能也会很大。这个时候，内存空间有限，那么就不得不将索引存储在磁盘中了。当然可以采用兼顾的方式，也就是一部分存储在内存中，一部分存储在磁盘上，这样就兼顾了内存消耗和查询效率。
- 单值查找还是区间查找。单值查找，也就是根据关键字查找等于某个值的数据。而区间查找则是指，要查找关键值处于某个区间的所有数据。比如在 MySQL 数据库中，就存在查找某个区间的数据。
- 单关键词查找还是多关键词组合查找。单关键词查找是指根据一个关键词进行查找，多关键词是指支持组合关键词查找。对于单关键词来说，索引构建起来相对简单些。对于多关键词查询来说，要分多种情况。比如针对 MySQL 这种结构化的数据，我们可以针对多个关键词的组合，建立索引，也就是索引的内容是多个关键词的组合；对于像搜索引擎这种非结构化的数据，我们可以针对单个关键构建索引，针对查询到的结果求并集或者交集，这样就可以得到多个关键词组合的查询结果了。
当然除了上述阐述的这些需求之外，还会有其他一些需求，上述这些都是相对共性的。
非功能性需求
- 不管是存储在内存中还是磁盘中，都需要让索引对存储空间的消耗不能过大。存储在内存中的话，消耗过大的话会占用存储空间的限制会非常苛刻。如果存储在硬盘中的，那索引对占用存储空间的限制会稍微放宽点，但是索引对存储空间的消耗可能也会超过原始数据。
- 在考虑索引查询效率的同时，还需要考虑索引的维护成本。索引的目的是提高查询效率，但是基于动态数据集合构建的索引，还需要考虑到索引的维护成本。因为，在对数据进行增加、删除、改动的同时，也需要对索引进行更新，这样才能保证之后查询的效率不会变得太低。但是，索引的更新操作势必会影响到增加、删除、改动的效率，这个额外增加的成本，需要考虑。
3.2. 构建索引常用的数据结构
前面对索引的一些需求进行了介绍，需要考虑的有：数据是格式化数据还是非格式化数据、数据是静态数据还是动态数据、索引存储在内存还是硬盘、单值查找还是区间查找、单关键词查找还是多关键词组合查找、索引对存储空间的消耗不能过大、索引的更新维护成本不能过高。
那么，下面我们开始考虑有哪些底层的数据结构可以用于索引。散列表、红黑树、跳表、B+树这些动态数据结构都常用于构建索引。位图、布隆过滤器可以作为辅助索引。有序数组可以用来对静态数据构建索引。
- 散列表增删改查操作的性能非常好，时间复杂度为 O(1)。一些键值数据库，比如 Redis，在构建索引的时候也使用了散列表（当然还用了跳表）。这类索引，一般都构建在内存中。
- 红黑树作为一种常用的平衡二叉查找树，增加、删除、查找的时间复杂度都是 O(logn)，也非常适合用于构建索引。Ext 文件系统中，对磁盘块的索引，用的就是红黑树。
- B+ 树相比红黑树来说，更适合构建存储在磁盘中的索引。B+ 树是一个多叉树，所以对相同个数的数据构建索引的话，B+ 树的高度要低于红黑树。那么，相应的磁盘操作的 IO 次数会更少。所以大部分关系型数据库的索引，比如 MySQL、Oracle，都是使用 B+ 树来实现的。
- 跳表也支持快速添加、删除、查找数据，时间复杂度是 O(logn)。而且我们可以通过灵活调整索引节点个数和数据个数之间的比例，来很好地平衡索引对内存的消耗以及查询效率。Redis 中的有序集合，就使用了跳表。
- 位图和布隆过滤器可以作为辅助，辅助存储在磁盘中的索引。布隆过滤器存在一定的误判率。但是，我们可以避免使用它的短处，而是使用它的长处，也就是对于判断不存在的数据那肯定是不存在的。那么，我们针对数据构建一个布隆过滤器，并且存储在内存中（布隆过滤器所占用的内存空间也是非常的少）。假如要查询一个数据的时候，我们可以先通过布隆过滤器，判断是否存在，如果不存在，那么数据肯定是不存在的了。那就没必要读取磁盘中的索引，对于那些数据不存在的情况，数据查询就更加快速了。
- 有序数组也可以作为索引，但是针对静态数据会更好。如果是静态的数据结构，也就是不会有插入、删除、更新操作，那么我们就可以根据关键来组织成一个有序数组，然后利用二分查找的方式来快速查找数据。
4. 总结
从上述的内容可以看出，架构师离不开数据结构和算法，在设计和实现的时候，尤其针对一些底层的设计需要考虑到它所使用的数据结构或者算法，从而提高性能。那些看似惊艳的架构设计思路，本质上都是来自最常用的数据结构和算法。
巨人的肩膀
- 极客时间-《数据结构与算法》-王争老师
