首先，该文章来自于极客时间网站，王争的专栏——《数据结构与算法之美》，我这里只是做简单的解释、记录并添加自己的见解，只是作为个人笔记，若侵权，马上删除。最后建议直接去该网站上购买该课程看原作者的讲解，一来是支持作者，二来是作者写的确实不错。
之前讲过，MySQL底层使用的是B+树这种数据结构，实现数据库索引的。那么类似 Redis 这样的 Key-Value 数据库中的索引，又是怎么实现的呢？底层依赖的又是什么数据结构呢？
本节讲述一下索引这种常用的技术解决思路，底层往往会依赖哪些数据结构。
为什么需要索引？
实际开发中，众多复杂的业务和功能的外壳，本质都可以抽象成“对数据的存储和计算”。对应到数据结构和算法中，那“存储”需要的就是数据结构，“计算”需要的就是算法。
对于存储的需求，功能上无外乎增删改查。这其实并不复杂，但是一旦存储的数据很多，那性能（存储性能、功能性能）就成了这些系统要关注的重点，特别是在一些跟存储相关的基础系统（比如 MySQL 数据库、分布式文件系统等）、中间件（比如消息中间件 RocketMQ 等）中。
“如何节省存储空间、如何提高数据增删改查的执行效率”，就成了设计的重点。而这些系统的实现，都离不开一个东西，那就是索引。不夸张地说，索引设计得好坏，直接决定了这些系统是否优秀。
索引的需求定义
要想设计一个系统，首先要搞明白其需求定义，一般从功能性需求和非功能性需求两方面来分析。
功能性需求
对于功能性需求需要考虑如下几点：
数据是格式化数据还是非格式化数据？要构建索引的原始数据，类型有很多。可以分为两类，一类是结构化数据，比如，MySQL 中的数据；另一类是非结构化数据，比如搜索引擎中网页。对于非结构化数据，一般需要做预处理，提取出查询关键词，对关键词构建索引。
数据是静态数据还是动态数据？若原始数据是一组静态数据，不会有数据的增删改操作，所以构建索引时只需要考虑查询的效率即可。不过，对于大部分情况要对动态数据构建索引，不仅要考虑到索引的查询效率，在原始数据更新的同时，还需要动态地更新索引。
索引存储在内存还是硬盘？索引存储在内存中，查询速度肯定比存储在硬盘上。但是若数据量很大，需要不得不把索引存储在硬盘中。除此之外，还有第三种情况，一部分存储在内存，一部分存储在磁盘，这样就可以兼顾内存消耗和查询效率。
单值查找还是区间查找？所谓单值查找，就是查询关键词等于某个值的数据。所谓区间查找，就是查找关键词处于某个区间值的所有数据。
单关键词查找还是多关键词组合查找？对于单关键词的查找，索引构建起来相对简单些。对于多关键词查询来说，要分多种情况。像 MySQL 这种结构化数据的查询需求，可以实现针对多个关键词的组合，建立索引；对于像搜索引擎这样的非结构数据的查询需求，可以针对单个关键词构建索引，然后通过集合操作，比如求并集、求交集等，计算出多个关键词组合的查询结果。
非功能性需求
不管是存储在内存中还是磁盘中，索引对存储空间的消耗不能过大。如果存储在内存中，索引对占用存储空间的限制就会非常苛刻。对于存储在硬盘中的索引，同样要注意，有时候索引对存储空间的消耗会超过原始数据。
在考虑索引查询效率的同时，还要考虑索引的维护成本。索引的目的是提高查询效率，但是，基于动态数据集合构建的索引，还要考虑到索引的维护成本。因为在原始数据动态增删改的同时，也需要动态的更新索引。而索引的更新势必会影响到增删改操作的性能。
构建索引常用的数据结构有哪些？
下面看看对于不同需求的索引结构，底层一般使用哪种数据结构？
实际上，常用来构建索引的数据结构，就是之前讲过的几种支持动态数据集合的数据结构。比如，散列表、红黑树、跳表、B+ 树。除此之外，位图、布隆过滤器可以作为辅助索引，有序数组可以用来对静态数据构建索引。
散列表增删改查操作的性能非常好，时间复杂度是 O(1)。一些键值数据库，比如 Redis、Memcache，就是使用散列表来构建索引的。这类索引，一般都构建在内存中。
红黑树作为一种常用的平衡二叉查找树，数据插入、删除、查找的时间复杂度是 $O(logn)$，也非常适合用来构建内存索引。Ext 文件系统中，对磁盘块的索引，用的就是红黑树。
B+ 树比起红黑树来说，更加适合构建存储在磁盘中的索引。B+ 树是一个多叉树，所以对相同个数的数据构建索引，B+ 树的高度要低于红黑树。当借助索引查询数据的时候，读取 B+ 树索引，需要的磁盘 IO 次数会更少。所以，大部分关系型数据库的索引，比如 MySQL、Oracle，都是用 B+ 树来实现的。
跳表也支持快速添加、删除、查找数据。而且，通过灵活调整索引结点个数和数据个数之间的比例，可以很好地平衡索引对内存的消耗及其查询效率。Redis 中的有序集合，就是用跳表来构建的。
除了散列表、红黑树、B+ 树、跳表之外，位图和布隆过滤器这两个数据结构，也可以用于索引中，辅助存储在磁盘中的索引，加速数据查找的效率。具体是怎么做的？
布隆过滤器有一定的判错率：对于判定存在的数据，有可能并不存在，但是对于判定不存在的数据，那肯定就不存在。而且，布隆过滤器还有一个更大的特点：内存占用非常少。所以可以针对数据，构建一个布隆过滤器，并且存储在内存中。当要查询数据时，可以先通过布隆过滤器，判定是否存在。如果通过布隆过滤器判定数据不存在，就没有必要读取磁盘中的索引了。对于数据不存在的情况，数据查询就更加快速了。
实际上，有序数组也可以被作为索引。如果数据是静态的，也就是不会有插入、删除、更新操作，那可以把数据的关键词（查询用的）抽取出来，组织成有序数组，然后利用二分查找算法来快速查找数据。
总结引申
本节从索引这个非常常用的技术方案，展示了散列表、红黑树、跳表、位图、布隆过滤器、有序数组这些数据结构的应用场景。
