转自：https://blog.csdn.net/every__day/article/details/90763607算法
《数据结构与算法之美》数据库
前面讲过MySQL数据库索引实现原理，底层是依赖B+树这种数据结构来实现的。那相似Redisp 这要的Key-Value数据库中的索引，又是怎么实现的呢?底层依赖的又是什么数据结构呢？数组
为何须要索引？
在实际的软件开发中，业务纷繁复杂，功能变幻无穷，可是，万变不离其宗。若是抛开业务和功能的外壳，其实它们的本质均可以抽象为“对数据的存储和计算”。对应到数据结构和算法中，那“存储”须要的就是数据结构，“计算”须要的就是算法。数据结构
对于存储的需求，功能上无外乎增删改查。这其实并不复杂。可是，一旦存储的数据多了，那性能就成了这些系统要关注的重点，特别是在一些跟存储相关的基础系统（好比MySQL数据库、分布式文件系统等）、中间件（好比消息中间件RocketMQ等）中。数据结构和算法
“如何节省存储空间、如何提升数据增删改查的执行效率”，这个问题就成了设计的重点。而这些系统的实现，都离不开一个东西，那就是索引。不夸张的说，索引设计的好坏，直接决定了这些系统是否优秀。分布式
索引这个概念，很是好理解。你能够类比书籍的目录来理解。若是没有目录，咱们想要查找某个知识点的时候，就要一页一页的翻。经过目录，咱们就能够快速定位相关的知识点的页数，查找的速度也会有质的提升。性能
索引的需求定义
索引的概念不难理解，在设计索引的过程当中，须要考虑一些因素，换名话说，咱们该如何定义清楚需求呢？搜索引擎
对于系统设计需求，咱们通常能够从功能性需求和非功能性需求两方面来分析。.net
1. 功能性需求设计
对于功能性需求大体要考虑如下几点。
数据是格式化的仍是非格式化数据？要构建索引的原始数据，类型不少。我把它分为两类，一类是结构化数据，好比MySQL中的数据；另外一类是非结构化数据，好比搜索引擎中的网页。对于非结构化数据，咱们通常须要作预处理，提取出查询关键词，对关键词构建索引。
数据是静态数据仍是动态数据？若是原始是一组静态数据，也就是说，不会有数据的增长、删除、更新操做，因此，咱们在构建索引的时候，只须要考虑查询效率就能够了。这样，索引的构建就相对简单些。不过，大部分状况下，咱们都是对动态数据构建索引，也就是说，咱们不只要考虑到索引的查询效率，在原始数据更新时，咱们还须要动态的更新索引。支持动态数据集合的索引，设计越来相对更复杂些。
索引是存储在内存仍是硬盘？若是索引存储在内存中，那技术要求的速度确定要比存储的磁盘中的高。可是，若是原始数据量很大的状况下，对应的索引可能也会很大。这个时候，由于内存有限，咱们可能就不得不将索引存储在硬盘中了。实际上，还有第三种状况，那就是一部分存储在内存，一部分存储在磁盘，这样就能够兼顾内存消耗和查询效率。
单值查找仍是区间查找？所谓单值查找，也就是根据查询关键词等于某个值的数据。这种查询需求最多见。所谓区间查找，就是查找关键词处于某个区间值的全部数据。实际上，不一样的应用场景，查询的需求会多种多样。
单关键词查找仍是多关键词组合查找？好比，搜索引擎中构建的索引，既要支持一个关键词的查找，好比“数据结构”，也要支持组合关键词查找，好比“数据结构 AND算法”。对于单关键词查找，索引构建起来相对简单些。对于多关键词查找来讲，要分多种状况。像MySQL这种结构化数据的查询需求，咱们能够实现针对多个关键词组合，创建索引；对于像搜索引擎这样的非结构数据的查询需求，咱们能够针对间个关键词构建索引，而后经过集合操做，好比求并集、求交集等，计算出多个关键词组合的查询结果。
实际上，不一样的场景，不一样的原始数据，对于索引的需求也会千差万别。
2.非功能性需求
不论是存储在内存中仍是磁盘中，索引对存储空间的消耗不能过大。若是存储在内存中，索引对占用存储空间的限制就会很是苛刻。毕竟内存空间很是有限，一个中间件启动后就占用几个GB的内存，开发者显然是没法接受的。若是存储在硬盘中，那索引对占用存储空间的限制，稍微会放宽一些。可是，咱们也不能掉以轻心。由于，有时候，索引对存储空间消耗会超过数据。
在考虑索引查询效率的同时，咱们仍是考虑索引的维护成本。索引的目的是提升查询效率，可是，基于动态数据集合构建的索引，咱们还要考虑到索引的维护成本。由于在原始数据动态增删改的同时，咱们也须要动态的更新索引。而索引的更新势必会影响到增删改的操做性能。
构建索引经常使用的数据结构有哪些？
实际上，经常使用来构建索引的数据结构，就是咱们以前讲过的几种支持动态数据集合的数据结构。好比，散列表、红黑树、跳表、B+树。除此以外，位图、布隆过滤器能够做为辅助索引，有序数组能够用来对静态数据构建索引。
咱们知道，散列表增删改查操做的性能很是好，时间复杂度是O(1)。一些键值数据库，好比Redis、Memcache，就是使用散列表来构建索引的。这类索引，通常都构建在内存中。
红黑树做为一种经常使用的平衡二叉查找树，数据插入、删除、查找的时间复杂度是O(logn)，也很是适合用来构建内存索引。Ext文件系统中，对磁盘块的索引，用的就是红黑树。
B+ 树比起红黑树来讲，更加适合构建存储在磁盘的索引。B+树是一个多叉树，因此，以相同个数的数据构建索引，B+树的高度要低于红黑树。当借助索引查询数据的时候，读取B+树索引，须要的磁盘IO次数更少。因此，大部分关系型数据库的索引，好比MySQL、Oracle，都是用B+树来实现的。
跳表也支持快速添加、删除、查找数据。并且，咱们经过灵活调整索引结点个数和数据个数之间的比例，能够很好的平衡对内存的消耗及其查询效率。Redis中的有序集合，就是用跳表来构建的。
除了散列表、红黑树、B+树、跳表以外，位图和布隆过滤器这两个数据结构，也能够用于索引中，辅助存储在磁盘中的索引，加速数据查询的效率。咱们来看下，具体是怎么作的？
布隆过滤器有必定的判错率。可是，咱们能够规避它的短处，发挥它的长处。尽管对于断定存在的数据，有可能并不存在，可是对于断定不存在的数据，那确定就不存在。并且，布隆过滤器还有一个更大的特色，那就是内存占用很是少。咱们能够针对数据，构建一个布隆过滤器，而且存储在内存中。当要查询数据的时候，咱们能够先经过布隆过滤器，断定是否存在。若是数据不存在，那咱们就不必读取磁盘中的索引了。对于数据不存在的状况，数据查询就更加快速了。
实际上，有序数组也能够被做为索引。若是数据是静态的，也就是不会插入、删除、更新操做，那咱们能够把数据的关键词（查询用的）抽取出来，组织成有序数组，而后利用二分查找算法来快速查找数据。