目录

数据结构和算法 | 索引是什么【高阶】

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. 总结

从上述的内容可以看出,架构师离不开数据结构和算法,在设计和实现的时候,尤其针对一些底层的设计需要考虑到它所使用的数据结构或者算法,从而提高性能。那些看似惊艳的架构设计思路,本质上都是来自最常用的数据结构和算法。

巨人的肩膀

  1. 极客时间-《数据结构与算法》-王争老师