50 | 索引：如何在海量数据中快速查找某个数据？

今天音频朗读帅哥把MySQL读成了 my s q l ，早上起来听音频，萌了\(//∇//)\

把数据的关键词（查询用的）抽取出来，组织成有序数组。如果关键词是整型，那索引就是整形数组，关键词是字符串，那索引就是字符串指针数组吗？

我对索引的理解 ------------ 索引真是个好东西。索引的英文名字叫：index，记住这个英文单词，会让我们更容易记忆和联想它到底是什么。在实际的编程中，index这个单词，真是到处可见。例如：数组的下标就是index 如果用一句话描述“索引”的作用，那会是什么？我想是这样：索引是用来辅助查找，用计算机专业术语叫：Addressing(寻址） 现实世界中，我们的查找会存在两种场景： 1. 从局部信息，查询与其相关的整体信息 2. 从整体信息中查询局部信息 怎么理解呢？ 搜索引擎需要查询一个网页中是否存在某个关键词以及通过某个关键词查询包含它的所有网页。 索引的应用 -------- 正是因为计算机大部分工作都是在Addressing，所以，在计算机中，索引到处存在。小到操作系统虚拟内存到真实内存的映射，就是索引嘛，大到分布式系统、网络，都是这个原理。 以上，我对索引的理解有点“广义”。我觉得数据结构和算法如此重要，它体现计算机精髓的地方便在于此。

es中的单排索引其实用了trie树，对每个需要索引的key维护了一个trie树，用于定位到这个key在文件中的位置， 然后直接用有序列表直接去访问对应的documents ，区块链拿以太坊来说吧，存储用的leveldb，数据存储用的数据结构是帕特利夏树，是一种高级的trie树，很好的做了数据的压缩， 消息中间件像kafka这种，会去做持久化，每个partition都会有很多数据，会有大量数据存储在磁盘中，所以每个partition也会有个索引，方便去做快速访问

谈一谈自己对数据结构和索引的理解： - 数据的存储，在底层只有两种形式：连续空间存储 和 零散空间存储，这两种形式对应了两种最基本的数据结构：数组 和 链表 - 使用这两种数据结构存储数据的空间利用率是最高的，但是如果想要实现更加快速的查找，我们就需要使用额外的操作，这两种操作是：用额外计算获取数据地址 和 用额外空间保持一种方便查找的结构。 - 用额外的计算获取数据地址，这种思路只能用于数组，因为数组的下标可以计算内存地址。具体应用如下： 1.使用数组下标进行数据的随机访问，这也是数组的杀手锏 2.通过对数据的计算确定数据应该存放的位置，这就是 散列表，这种计算方法就是哈希函数 - 用额外的空间保持方便查找的结构，这种思路用于“使用零散空间存储数据的情况”，你仔细思考，跳表、红黑树、B+树 是不是都是这种思路的产儿？ 1.跳表通过设置额外的节点索引，实现了加快数据查询的功能。 2.红黑树、B+树 通过树这种结构用不同孩子保存了不同数据间的关系。 - 不同数据结构的组合可以实现更多功能。 - 如果想实现范围索引，最好的办法是使用有序链表，我们通过某种方法，找到数据范围中的起始结点，然后通过有序链表依次输出范围内的结点，直到数据超出范围，这里有几个现成的例子： 1.跳表：通过额外的结点找到有序链表的起始结点，然后依次输出 2.B+树：通过查找叶子节点定位有序链表的起始节点，然后依次输出

可以讲讲es 到排序索引结构原理和数据结构？

昨天刚学了操作系统的多级页表，应该是比较经典的索引了😂

从评论可以看出能坚持到这里的人不多，不过也不绝对，因为有些坚持到这里的人可能因为某些原因没有发表评论。不过还是很感谢老师的，从这个课程中，我体会到了数据结构的用处。之前有人说数据结构在平常的开发中没有用，当时我表示认同。现在看来，这句话也不完全正确。不同层次的人看问题的思路不同，结果也南辕北辙。

为什么需要索引？ （1）在实际的软件开发工作的本质都可以抽象为“对数据的存储和计算”。对应到数据结构和算法中，那“存储”需要的就是数据结构，“计算”需要的就是算法。 （2）对于存储的需求，功能上无外乎增删改查。当存储的数据很多，性能就会成为这些系统要关注的重点，特别是在存储相关的基础系统、中间件中。 （3）“如何节省存储空间、如何提高数据增删改查的执行效率”，解决这样的问题离不开索引 索引的需求定义 对于系统设计需求，一般可以从功能性需求和非功能性需求两方面来分析 1. 功能性需求 （1）数据是格式化数据还是非格式化数据？ 构建索引的原始数据，可分为两类： * 一类是结构化数据，如MySQL 中的数据； * 一类是非结构化数据，如搜索引擎中网页。非结构化数据，一般需要预处理，提取出查询关键词，对关键词构建索引。 （2）数据是静态数据还是动态数据？ * 如果是一组静态数据，在构建索引时只需考虑查询效率 * 动态数据构建索引，不仅要考虑索引的查询效率，在原始数据更新的同时，还需要动态地更新索引 （3）索引存储在内存还是硬盘？ * 当数据量小时，索引可以存储在内存中。 * 原始数据量很大时，对应的索引可能也会很大。内存有限，可能需要将索引存储在磁盘中。 * 第三种情况：一部分存储在内存，一部分存储在磁盘，这样可以兼顾内存消耗和查询效率。 （4）单值查找还是区间查找？ * 所谓单值查找，也就是根据查询关键词等于某个值的数据。 * 所谓区间查找，就是查找关键词处于某个区间值的所有数据。不同的应用场景，查询的需求会多种多样。 （5）单关键词查找还是多关键词组合查找？ * 对于单关键词的查找，索引构建起来相对简单。 * 多关键词查询要分多种情况: A：像 MySQL 这种结构化数据的查询，可以实现针对多个关键词的组合，建立索引； B：像搜索引擎这样的非结构数据的查询，可以针对单个关键词构建索引，然后通过集合操作，如求并集、求交集等，计算出多个关键词组合的查询结果。 不同的场景，不同的原始数据，对于索引的需求也会千差万别 2. 非功能性需求 （1）不管是存储在内存中还是磁盘中，索引对存储空间的消耗不能过大。 * 如果存储在内存中，索引对占用存储空间的限制就会非常苛刻 * 如果存储在硬盘中，也不能掉以轻心，因为有时索引对存储空间的消耗会超过原始数据 （2）在考虑索引查询效率的同时，还要考虑索引的维护成本。 * 基于动态数据集合构建的索引要考虑索引的维护成本。因为在原始数据动态增删改的同时，也需要动态的更新索引。而索引的更新势必会影响到增删改操作的性能。 构建索引常用的数据结构有哪些？ 如散列表、红黑树、跳表、B+ 树，除此之外，位图、布隆过滤器可以作为辅助索引，有序数组可以用来对静态数据构建索引 * 散列表增删改查操作的时间复杂度是 O(1)，被一些键值数据库用来构建索引，如 Redis、Memcache。这类索引，一般都构建在内存中。 * 红黑树是常用的平衡二叉查找树，数据插入、删除、查找的时间复杂度是 O(logn)，也非常适合用来构建内存索引。Ext 文件系统中，对磁盘块的索引，用的就是红黑树。 * B+ 树比起红黑树更加适合构建存储在磁盘中的索引 （1）B+ 树是一个多叉树，对相同个数的数据构建索引，B+ 树的高度要低于红黑树。 （2）当借助索引查询数据时，读取 B+ 树索引需要的磁盘 IO 次数会更少。 所以，如 MySQL、Oracle等，大部分关系型数据库的索引都是用 B+ 树来实现的 * 跳表也支持快速添加、删除、查找数据，通过调整索引结点个数和数据个数之间的比例，可以很好地平衡索引对内存的消耗及其查询效率。Redis 中的有序集合，就是用跳表来构建的 * 布隆过滤器有一定的判错率，但可以规避它的短处，发挥它的长处 （1）尽管对于判定存在的数据可能并不存在，但是对于判定不存在的数据是一定不存在 （2）布隆过滤器有个大特点：内存占用非常少，所以可以针对数据，构建一个布隆过滤器存储在内存中。 （3）查询数据时，如果布隆过滤器判定数据不存在，就不必读取磁盘中的索引了。对于数据不存在的情况，数据查询就更加快速了。 * 有序数组也可以被作为索引，如果数据是静态的只有查询操作，可以把数据的关键词（查询用的）抽取出来，组织成有序数组，然后利用二分查找算法来快速查找数据。

我以前只是人云亦云地认同“数据结构和算法”十分重要。看完本节，豁然开朗。似乎庞大的计算机体系，将其本质，半隐半现地展示在我面前