数据结构与算法之美笔记之索引、并行算法

索引

索引就像书的目录，通过目录，我们就可以快速定位相关知识点的页数，查找的速度也会有质的提高。

---

索引的需求定义

1. 功能性需求（作者谈到的几种）
   • 数据是格式化数据还是非格式化数据？对于非结构化数据，我们一般需要做预处理，提取出查询关键词，对关键词构建索引。
   • 数据是静态数据还是动态数据？静态数据就相对简单，动态索引就不仅要考虑他的查询效率，还要考虑索引更新效率
   • 索引存储在内存还是硬盘？内存中操作速度肯定快些，但是如果数据量太大，索引就需要存在磁盘里了，当然我们也可以将索引一部分存在内存一部分存在磁盘
   • 单值查找还是区间查找？
   • 单关键词查找还是多关键词组合查找？比如，搜索引擎中构建的索引，既要支持一个关键词的查找，比如“数据结构”，也要支持组合关键词查找，比如“数据结构 AND 算法”。对于多关键词查询来说，要分多种情况。像MySQL这种结构化数据的查询需求，我们可以实现针对多个关键词的组合，建立索引；对于像搜索引擎这样的非结构数据的查询需求，我们可以针对单个关键词构建索引，然后通过集合操作，比如求并集、求交集等，计算出多个关键词组合的查询结果。
2. 非功能性需求

• 索引对存储空间的消耗不能过大。因为有时候，索引对存储空间的消耗会超过原始数据。
• 在考虑索引查询效率的同时，我们还要考虑索引的维护成本。索引的更新势必会影响到增删改操作的性能。

---

构建索引常用的数据结构

• 散列表
  我们知道，散列表增删改查操作的性能非常好，时间复杂度是O(1)。一些键值数据库，比如Redis、Memcache，就是使用散列表来构建索引的。这类索引，一般都构建在内存中。

• 红黑树
  红黑树作为一种常用的平衡二叉查找树，数据插入、删除、查找的时间复杂度是O(logn)，也非常适合用来构建内存索引。Ext文件系统中，对磁盘块的索引，用的就是红黑树。

• B+树
  B+树比起红黑树来说，更加适合构建存储在磁盘中的索引。B+树是一个多叉树，所以，对相同个数的数据构建索引，B+树的高度要低于红黑树。当借助索引查询数据的时候，读取B+树索引，需要的磁盘IO次数非常更少。所以，大部分关系型数据库的索引，比如MySQL、Oracle，都是用B+树来实现的。

• 跳表
  跳表也支持快速添加、删除、查找数据。而且，我们通过灵活调整索引结点个数和数据个数之间的比例，可以很好地平衡索引对内存的消耗及其查询效率。Redis中的有序集合，就是用跳表来构建的。

• 布隆过滤器
  我们知道，布隆过滤器有一定的判错率。但是，我们可以规避它的短处，发挥它的长处。尽管对于判定存在的数据，有可能并不存在，但是对于判定不存在的数据，那肯定就不存在。而且，布隆过滤器还有一个更大的特点，那就是内存占用非常少。我们可以针对数据，构建一个布隆过滤器，并且存储在内存中。当要查询数据的时候，我们可以先通过布隆过滤器，判定是否存在。如果通过布隆过滤器判定数据不存在，那我们就没有必要读取磁盘中的索引了。对于数据不存在的情况，数据查询就更加快速了。

• 有序数组
  有序数组也可以被作为索引。如果数据是静态的，也就是不会有插入、删除、更新操作，比如去年的xx数据，那我们可以把数据的关键词（查询用的）抽取出来，组织成有序数组，然后利用二分查找算法来快速查找数据。

---

并行算法

当算法无法再继续优化的情况下，我们该如何来进一步提高执行效率呢？

• 并行排序
  比如归并排序，我们把8GB的数据分成16个文件，再用16个文件分别排序完，再对这16个有序集合合并，快排的原理也是分治，
  它们的区别在于，第一种处理思路是，先随意地对数据分片，排序之后再合并。第二种处理思路是，先对数据按照大小划分区间，然后再排序，排完序就不需要再处理了。
• 并行查找
  将数据分到多个散列表中，再开多个线程分别在各自的散列表内查找，插入元素就是把元素插入装载因子最小的那个散列表中，这样有助于减少散列冲突。
• 并行字符串匹配
• 并行搜索

并行计算是一个工程上的实现思路，尽管跟算法关系不大，但是，在实际的软件开发中，它确实可以非常巧妙地提高程序的运行效率，是一种非常好用的性能优化手段。

特别是，当要处理的数据规模达到一定程度之后，我们无法通过继续优化算法，来提高执行效率 的时候，我们就需要在实现的思路上做文章，利用更多的硬件资源，来加快执行的效率。所以，在很多超大规模数据处理中，并行处理的思想，应用非常广泛，比如MapReduce实际上就是一种并行计算框架。