算法之美5 - 树

青旅半醒 2022-03-01 15:52 252阅读 0赞

## 树 ##

二叉树、多路查找树、堆、树状数组、线段树

--------------------

### 23 | 二叉树基础（上）：什么样的二叉树适合用数组来存储？ ###

树 - 二叉树 - 满二叉树 - 完全二叉树

> 完全二叉树

![18413c6597c2850b75367393b401ad60.jpg][]

> 二叉树的存储

想要存储一棵二叉树，我们有两种方法，一种是基于指针或者引用的二叉**链式存储**法，一种是基于数组的**顺序存储**法。

> 小结

非线性表数据结构，树。关于树，有几个比较常用的概念你需要掌握，那就是：根节点、叶子节点、父节点、子节点、兄弟节点，还有节点的高度、深度、层数，以及树的高度。

![4094a733986073fedb6b9d03f877d71e.jpg][]

举例：

![50f89510ad1f7570791dd12f4e9adeb4.jpg][]

我们平时最常用的树就是二叉树。二叉树的每个节点最多有两个子节，分别是左子节点和右子节点。二叉树中，有两种比较特殊的树，分别是满二叉树和完全二叉树。满二叉树又是完全二叉树的一种特殊情况。

二叉树既可以用链式存储，也可以用数组顺序存储。\*\*数组顺序存储的方式比较适合完全二叉树，其他类型的二叉树用数组存储会比较浪费存储空间。\*\*除此之外，二叉树里非常重要的操作就是前、中、后序遍历操作，遍历的时间复杂度是 O(n)，你需要理解并能用递归代码来实现。

> 思考

1.给定一组数据，比如 1，3，5，6，9，10。你来算算，可以构建出多少种不同的二叉树？

2.我们讲了三种二叉树的遍历方式，前、中、后序。实际上，还有另外一种遍历方式，也就是按层遍历，你知道如何实现吗？

--------------------

### 24 | 二叉树基础（下）：有了如此高效的散列表，为什么还需要二叉树？ ###

> 解答开篇

我们在散列表那节中讲过，散列表的插入、删除、查找操作的时间复杂度可以做到常量级的 O(1)，非常高效。而二叉查找树在比较平衡的情况下，插入、删除、查找操作时间复杂度才是 O(logn)，相对散列表，好像并没有什么优势，那我们为什么还要用二叉查找树呢？

我认为有下面几个原因：

第一，散列表中的数据是**无序**存储的，如果要输出有序的数据，需要先进行排序。而对于二叉查找树来说，我们只需要中序遍历，就可以在 O(n) 的时间复杂度内，输出有序的数据序列。

第二，散列表扩容耗时很多，而且当遇到散列冲突时，性能**不稳定**，尽管二叉查找树的性能不稳定，但是在工程中，我们最常用的平衡二叉查找树的性能非常稳定，时间复杂度稳定在 O(logn)。

第三，笼统地来说，尽管散列表的查找等操作的时间复杂度是常量级的，但因为哈希冲突的存在，这个常量不一定比 logn 小，所以实际的查找速度可能不一定比 O(logn) 快。加上哈希函数的耗时，也不一定就比平衡二叉查找树的**效率**高。

第四，散列表的**构造**比二叉查找树要复杂，需要考虑的东西很多。比如散列函数的设计、冲突解决办法、扩容、缩容等。平衡二叉查找树只需要考虑平衡性这一个问题，而且这个问题的解决方案比较成熟、固定。

最后，为了避免过多的散列冲突，散列表装载因子不能太大，特别是基于开放寻址法解决冲突的散列表，不然会浪费一定的存储**空间**。

> 内容小结

今天我们学习了一种特殊的二叉树，二叉查找树。它支持快速地查找、插入、删除操作。

二叉查找树中，每个节点的值都大于左子树节点的值，小于右子树节点的值。不过，这只是针对没有重复数据的情况。对于存在重复数据的二叉查找树，我介绍了两种构建方法，一种是让每个节点存储多个值相同的数据；另一种是，每个节点中存储一个数据。针对这种情况，我们只需要稍加改造原来的插入、删除、查找操作即可。

在二叉查找树中，查找、插入、删除等很多操作的时间复杂度都跟树的高度成正比。两个极端情况的时间复杂度分别是 O(n) 和 O(logn)，分别对应二叉树退化成链表的情况和完全二叉树。

为了避免时间复杂度的退化，针对二叉查找树，我们又设计了一种更加复杂的树，平衡二叉查找树，时间复杂度可以做到稳定的 O(logn)，下一节我们下一节我们具体来讲。

> 课后思考

今天我讲了二叉树高度的理论分析方法，给出了粗略的数量级。如何通过编程，求出一棵给定二叉树的确切高度呢？

递归法，根节点高度=max(左子树高度，右子树高度)+1

> 知识关联

链表 -(两个指针)-> 二叉树 -(查找)-> 二叉查找树 -(稳定性)-> 平衡二叉查找树

链表 -(多个指针)-> 图

--------------------

### 25 | 红黑树（上）：为什么工程中都用红黑树这种二叉树？ ###

> 什么是“平衡二叉查找树”？

平衡二叉树的严格定义是这样的：二叉树中**任意一个节点的左右子树的高度相差不能大于 1**。从这个定义来看，上一节我们讲的完全二叉树、满二叉树其实都是平衡二叉树，但是非完全二叉树也有可能是平衡二叉树。

![dd9f5a4525f5029a8339c89ad1c8159b.jpg][]

平衡二叉查找树不仅满足上面平衡二叉树的定义，还满足二叉查找树的特点。最先被发明的平衡二叉查找树是**AVL 树**，它严格符合我刚讲到的平衡二叉查找树的定义，即任何节点的左右子树高度相差不超过 1，是一种高度平衡的二叉查找树。

但是很多平衡二叉查找树其实并没有严格符合上面的定义（树中任意一个节点的左右子树的高度相差不能大于 1），比如我们下面要讲的红黑树，它从根节点到各个叶子节点的最长路径，有可能会比最短路径大一倍。

发明平衡二叉查找树这类数据结构的初衷是，**解决普通二叉查找树在频繁的插入、删除等动态更新的情况下，出现时间复杂度退化的问题**。

平衡二叉查找树中“平衡”的意思，其实就是让整棵树左右看起来比较“对称”、比较“平衡”，不要出现左子树很高、右子树很矮的情况。这样就能让整棵树的高度相对来说低一些，相应的插入、删除、查找等操作的效率高一些。

> 如何定义一棵“红黑树”？

平衡二叉查找树其实有很多，比如，Splay Tree（伸展树）、Treap（树堆）等，但是我们提到平衡二叉查找树，听到的基本都是红黑树。它的出镜率甚至要高于“平衡二叉查找树”这几个字，有时候，我们甚至默认平衡二叉查找树就是红黑树，那我们现在就来看看这个“明星树”。

红黑树的英文是“Red-Black Tree”，简称 R-B Tree。它是一种**不严格的平衡二叉查找树**，我前面说了，它的定义是不严格符合平衡二叉查找树的定义的。那红黑树究竟是怎么定义的呢？

顾名思义，红黑树中的节点，一类被标记为黑色，一类被标记为红色。除此之外，一棵红黑树还需要满足这样几个要求：

*  根节点是黑色的；
 *  每个叶子节点都是黑色的空节点（NIL），也就是说，叶子节点不存储数据；（简化红黑树的代码实现）
 *  任何相邻的节点都不能同时为红色，也就是说，红色节点是被黑色节点隔开的；
 *  每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同数目的黑色节点；

为了让你更好地理解上面的定义，我画了两个红黑树的图例，你可以对照着看下。

![903ee0dcb62bce2f5b47819541f9069a.jpg][]

> 为什么说红黑树是“近似平衡”的？

我们前面也讲到，平衡二叉查找树的初衷，是为了解决二叉查找树因为动态更新导致的性能退化问题。所以，“平衡”的意思可以等价为性能不退化。“近似平衡”就等价为性能不会退化的太严重。

首先，我们来看，如果我们将红色节点从红黑树中去掉，那单纯包含黑色节点的红黑树的高度是多少呢？

红色节点删除之后，有些节点就没有父节点了，它们会直接拿这些节点的祖父节点（父节点的父节点）作为父节点。所以，之前的二叉树就变成了四叉树。

![7e6ecc308fe44120f30de809822215ed.jpg][]

前面红黑树的定义里有这么一条：从任意节点到可达的叶子节点的每个路径包含相同数目的黑色节点。我们从四叉树中取出某些节点，放到叶节点位置，四叉树就变成了完全二叉树。所以，仅包含黑色节点的四叉树的高度，比包含相同节点个数的完全二叉树的高度还要小。

完全二叉树的高度近似 log2n，这里的四叉“黑树”的高度要低于完全二叉树，所以去掉红色节点的“黑树”的高度也不会超过 log2n。

我们现在知道只包含黑色节点的“黑树”的高度，那我们现在把红色节点加回去，高度会变成多少呢？

从上面我画的红黑树的例子和定义看，在红黑树中，红色节点不能相邻，也就是说，有一个红色节点就要至少有一个黑色节点，将它跟其他红色节点隔开。红黑树中包含最多黑色节点的路径不会超过 log2n，所以加入红色节点之后，最长路径不会超过 2log2n，也就是说，红黑树的高度近似 2log2n。

所以，红黑树的高度只比高度平衡的 AVL 树的高度（log2n）仅仅大了一倍，在性能上，下降得并不多。这样推导出来的结果不够精确，实际上红黑树的性能更好。

> 开篇解答

我们前面提到 Treap、Splay Tree，绝大部分情况下，它们操作的**效率**都很高，但是也无法避免极端情况下时间复杂度的退化。尽管这种情况出现的概率不大，但是对于单次操作时间非常敏感的场景来说，它们并不适用。

AVL 树是一种高度平衡的二叉树，所以查找的效率非常高，但是，有利就有弊，AVL 树为了维持这种高度的平衡，就要付出更多的代价。每次插入、删除都要做调整，就比较复杂、耗时。所以，对于有频繁的插入、删除操作的数据集合，使用 AVL 树的**代价**就有点高了。

红黑树只是做到了**近似平衡**，并不是严格的平衡，所以在维护平衡的成本上，要比 AVL 树要低。

所以，**红黑树的插入、删除、查找各种操作性能都比较稳定**。对于工程应用来说，要面对各种异常情况，为了支撑这种工业级的应用，我们更倾向于这种性能稳定的平衡二叉查找树。

> 内容小结

我们学习数据结构和算法，要学习它的由来、特性、适用的场景以及它能解决的问题。对于红黑树，也不例外。你如果能搞懂这几个问题，其实就已经足够了。

红黑树是一种平衡二叉查找树。它是为了**解决普通二叉查找树在数据更新的过程中，复杂度退化的问题而产生的**。红黑树的高度近似 log2n，所以它是近似平衡，插入、删除、查找操作的时间复杂度都是 **O(logn)**。

因为红黑树是一种性能非常**稳定**的二叉查找树，所以，在工程中，但凡是用到动态插入、删除、查找数据的场景，都可以用到它。不过，它实现起来比较复杂，如果自己写代码实现，难度会有些高，这个时候，我们其实更倾向用跳表来替代它。

> 课后思考

动态数据结构支持动态地数据插入、删除、查找操作，除了红黑树，我们前面还学习过哪些呢？能对比一下各自的优势、劣势，以及应用场景吗？

--------------------

### 26 | 红黑树（下）：掌握这些技巧，你也可以实现一个红黑树 ###

> 实现红黑树的基本思想

实际上，红黑树的平衡过程跟魔方复原非常神似，大致过程就是：遇到什么样的节点排布，我们就对应怎么去调整。

左旋（rotate left）& 右旋（rotate right）

![0e37e597737012593a93105ebbf4591e.jpg][]

> 插入操作的平衡调整

红黑树规定，插入的节点必须是红色的。而且，二叉查找树中新插入的节点都是放在叶子节点上。所以，关于插入操作的平衡调整，有这样两种特殊情况，但是也都非常好处理。

*  如果插入节点的父节点是黑色的，那我们什么都不用做，它仍然满足红黑树的定义。
 *  如果插入的节点是根节点，那我们直接改变它的颜色，把它变成黑色就可以了。

除此之外，其他情况都会违背红黑树的定义，于是我们就需要进行调整，调整的过程包含两种基础的操作：**左右旋转**和**改变颜色**。

红黑树的平衡调整过程是一个迭代的过程。我们把正在处理的节点叫作关注节点。关注节点会随着不停地迭代处理，而不断发生变化。最开始的关注节点就是新插入的节点。

新节点插入之后，如果红黑树的平衡被打破，那一般会有下面三种情况。我们只需要根据每种情况的特点，不停地调整，就可以让红黑树继续符合定义，也就是继续保持平衡。

CASE 1：如果关注节点是 a，它的叔叔节点 d 是红色

![603cf91f54b5db21bd02c6c5678ecf40.jpg][]

CASE 2：如果关注节点是 a，它的叔叔节点 d 是黑色，关注节点 a 是其父节点 b 的右子节点

![4480a314f9d83c343b8adbb28b6782ad.jpg][]

CASE 3：如果关注节点是 a，它的叔叔节点 d 是黑色，关注节点 a 是其父节点 b 的左子节点

![04650d9470b1e67899f5b8b7b8e33212.jpg][]

> 删除操作的平衡调整

删除操作的平衡调整分为两步，第一步是**针对删除节点初步调整**。初步调整只是保证整棵红黑树在一个节点删除之后，仍然满足最后一条定义的要求，也就是说，每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同数目的黑色节点；第二步是**针对关注节点进行二次调整**，让它满足红黑树的第三条定义，即不存在相邻的两个红色节点。

1、针对删除节点初步调整

CASE 1：如果要删除的节点是 a，它只有一个子节点 b

![a6c4c347b7cbdf57662bab399ed36cc3.jpg][]

CASE 2：如果要删除的节点 a 有两个非空子节点，并且它的后继节点就是节点 a 的右子节点 c

![48e3bd2cdd66cb635f8a4df8fb8fd64e.jpg][]

CASE 3：如果要删除的是节点 a，它有两个非空子节点，并且节点 a 的后继节点不是右子节点

![b93c1fa4de16aee5482424ddf49f3c29.jpg][]

2、针对关注节点进行二次调整

CASE 1：如果关注节点是 a，它的兄弟节点 c 是红色的

![ac76d78c064a2486e2a5b4c4903acb91.jpg][]

CASE 2：如果关注节点是 a，它的兄弟节点 c 是黑色的，并且节点 c 的左右子节点 d、e 都是黑色的

![eca118d673c607eb2b103f3476fb24ec.jpg][]

CASE 3：如果关注节点是 a，它的兄弟节点 c 是黑色，c 的左子节点 d 是红色，c 的右子节点 e 是黑色

![44075213100edd70315e1492422c92af.jpg][]

CASE 4：如果关注节点 a 的兄弟节点 c 是黑色的，并且 c 的右子节点是红色的

![5f73f61bf77a7f2bb75f168cf432ec44.jpg][]

> 内容小结

现在，我就来总结一下，如何比较轻松地看懂我今天讲的操作过程。

*  把红黑树的平衡调整的过程比作魔方复原，不要过于深究这个算法的正确性
 *  找准关注节点，不要搞丢、搞错关注节点
 *  插入操作的平衡调整比较简单，但是删除操作就比较复杂

--------------------

### 48 | B+树：MySQL数据库索引是如何实现的？ ###

问题：数据库索引是如何实现的呢？底层使用的是什么数据结构和算法呢？

> 1.解决问题的前提是定义清楚问题

如果你对数据库的操作非常了解，针对我们现在这个问题，你就能把索引的需求定义得非常清楚。但是，对于大部分软件工程师来说，我们可能只了解一小部分常用的 SQL 语句，所以，这里我们假设要解决的问题，只包含这样两个常用的需求：

*  根据某个**值**查找数据，比如 select \* from user where id=1234；
 *  根据**区间**值来查找某些数据，比如 select \* from user where id > 1234 and id < 2345。

对一些模糊的需求进行假设，来限定要解决的问题的范围

性能方面的需求。性能方面的需求，我们主要考察时间和空间两方面，也就是**执行效率和存储空间**

> 2.尝试用学过的数据结构解决这个问题

问题的需求大致定义清楚了，我们现在回想一下，能否利用已经学习过的数据结构解决这个问题呢？支持快速查询、插入等操作的动态数据结构，我们已经学习过**散列表、平衡二叉查找树、跳表**。

我们先来看散列表。散列表的查询性能很好，时间复杂度是 O(1)。但是，散列表不能支持按照区间快速查找数据。所以，散列表不能满足我们的需求。

我们再来看平衡二叉查找树。尽管平衡二叉查找树查询的性能也很高，时间复杂度是 O(logn)。而且，对树进行中序遍历，我们还可以得到一个从小到大有序的数据序列，但这仍然不足以支持按照区间快速查找数据。

我们再来看跳表。跳表是在链表之上加上多层索引构成的。它支持快速地插入、查找、删除数据，对应的时间复杂度是 O(logn)。并且，跳表也支持按照区间快速地查找数据。我们只需要定位到区间起点值对应在链表中的结点，然后从这个结点开始，顺序遍历链表，直到区间终点对应的结点为止，这期间遍历得到的数据就是满足区间值的数据。

![492206afe5e2fef9f683c7cff83afa65.jpg][]

这样看来，跳表是可以解决这个问题。实际上，数据库索引所用到的数据结构跟跳表非常相似，叫作 B+ 树。不过，它是通过二叉查找树演化过来的，而非跳表。为了给你还原发明 B+ 树的整个思考过程，所以，接下来，我还再从二叉查找树讲起，看它是如何一步一步被改造成 B+ 树的。

> 3.改造二叉查找树来解决这个问题

为了让二叉查找树支持按照区间来查找数据，我们可以对它进行这样的改造：**树中的节点并不存储数据本身**，而是只是作为索引。除此之外，我们把每个**叶子节点串在一条链表上**，链表中的数据是从小到大有序的。经过改造之后的二叉树，就像图中这样，看起来是不是很像跳表呢？

![25700c1dc28ce094eed3ffac394531f4.jpg][]

改造之后，如果我们要求某个区间的数据。

![1cf179c03c702a6ef5b9336f5b1eaecc.jpg][]

但是，我们要为几千万、上亿的数据构建索引，如果将索引存储在内存中，尽管内存访问的速度非常快，查询的效率非常高，但是，占用的内存会非常多。

比如，我们给一亿个数据构建二叉查找树索引，那索引中会包含大约 1 亿个节点，每个节点假设占用 16 个字节，那就需要大约 1GB 的内存空间。给一张表建立索引，我们需要 1GB 的内存空间。如果我们要给 10 张表建立索引，那对内存的需求是无法满足的。如何解决这个索引占用太多内存的问题呢？

我们可以借助时间换空间的思路，**把索引存储在硬盘中**，而非内存中。我们都知道，硬盘是一个非常慢速的存储设备。通常内存的访问速度是纳秒级别的，而磁盘访问的速度是毫秒级别的。读取同样大小的数据，从磁盘中读取花费的时间，是从内存中读取所花费时间的上万倍，甚至几十万倍。

二叉查找树，经过改造之后，支持区间查找的功能就实现了。不过，为了节省内存，如果把树存储在硬盘中，那么每个节点的读取（或者访问），都对应一次磁盘 IO 操作。树的高度就等于每次查询数据时磁盘 IO 操作的次数。

我们前面讲到，比起内存读写操作，磁盘 IO 操作非常耗时，所以我们优化的重点就是尽量减少磁盘 IO 操作，也就是，尽量降低树的高度。那如何降低树的高度呢？

我们来看下，如果我们**把索引构建成 m 叉树**，高度是不是比二叉树要小呢？如图所示，给 16 个数据构建二叉树索引，树的高度是 4，查找一个数据，就需要 4 个磁盘 IO 操作（如果根节点存储在内存中，其他结点存储在磁盘中），如果对 16 个数据构建五叉树索引，那高度只有 2，查找一个数据，对应只需要 2 次磁盘操作。如果 m 叉树中的 m 是 100，那对一亿个数据构建索引，树的高度也只是 3，最多只要 3 次磁盘 IO 就能获取到数据。磁盘 IO 变少了，查找数据的效率也就提高了。

![69d4c48c1257dcb7dd6077d961b86259.jpg][]

对于相同个数的数据构建 m 叉树索引，m 叉树中的 m 越大，那树的高度就越小，那 m 叉树中的 m 是不是越大越好呢？到底多大才最合适呢？

不管是内存中的数据，还是磁盘中的数据，操作系统都是**按页**（一页大小通常是 4KB，这个值可以通过 getconfig PAGE\_SIZE 命令查看）来读取的，一次会读一页的数据。如果要读取的数据量超过一页的大小，就会触发多次 IO 操作。所以，我们在选择 m 大小的时候，要尽量让每个节点的大小等于一个页的大小。读取一个节点，只需要一次磁盘 IO 操作。

![ea4472fd7bb7fa948532c8c8ba334430.jpg][]

尽管索引可以提高数据库的查询效率，但是，作为一名开发工程师，你应该也知道，索引有利也有弊，它也会让写入数据的效率下降。这是为什么呢？

数据的写入过程，会涉及索引的更新，这是索引导致**写入变慢**的主要原因。

对于一个 B+ 树来说，m 值是根据页的大小事先计算好的，也就是说，每个节点最多只能有 m 个子节点。在往数据库中写入数据的过程中，这样就有可能使索引中某些节点的子节点个数超过 m，这个节点的大小超过了一个页的大小，读取这样一个节点，就会导致多次磁盘 IO 操作。我们该如何解决这个问题呢？

实际上，处理思路并不复杂。我们只需要将这个节点**分裂**成两个节点。但是，节点分裂之后，其上层父节点的子节点个数就有可能超过 m 个。不过这也没关系，我们可以用同样的方法，将父节点也分裂成两个节点。这种级联反应会**从下往上**，一直影响到根节点。这个分裂过程，你可以结合着下面这个图一块看，会更容易理解（图中的 B+ 树是一个三叉树。我们限定叶子节点中，数据的个数超过 2 个就分裂节点；非叶子节点中，子节点的个数超过 3 个就分裂节点）。

![1800bc80e1e05b32a042ff6873e6c2e0.jpg][]

正是因为要时刻保证 B+ 树索引是一个 m 叉树，所以，索引的存在会导致数据库写入的速度降低。实际上，不光写入数据会变慢，**删除数据也会变慢**。这是为什么呢？

我们在删除某个数据的时候，也要对应的更新索引节点。这个处理思路有点类似跳表中删除数据的处理思路。频繁的数据删除，就会导致某些结点中，子节点的个数变得非常少，长此以往，如果每个节点的子节点都比较少，势必会影响索引的效率。

我们可以设置一个阈值。在 B+ 树中，这个阈值等于 m/2。如果某个节点的子节点个数小于 m/2，我们就将它跟相邻的兄弟节点合并。不过，合并之后结点的子节点个数有可能会超过 m。针对这种情况，我们可以借助插入数据时候的处理方法，再分裂节点。

文字描述不是很直观，我举了一个删除操作的例子，你可以对比着看下（图中的 B+ 树是一个五叉树。我们限定叶子节点中，数据的个数少于 2 个就合并节点；非叶子节点中，子节点的个数少于 3 个就合并节点。）。

![1730e34450dad29f062e76536622c918.jpg][]

> 总结一下 B+ 树的特点

*  每个节点中子节点的个数不能超过 m，也不能小于 m/2；
 *  根节点的子节点个数可以不超过 m/2，这是一个例外；
 *  m 叉树只存储索引，并不真正存储数据，这个有点儿类似跳表；
 *  通过链表将叶子节点串联在一起，这样可以方便按区间查找；
 *  一般情况，根节点会被存储在内存中，其他节点存储在磁盘中。

> B 树 & B + 树

除了 B+ 树，你可能还听说过 B 树、B- 树，我这里简单提一下。实际上，B- 树就是 B 树，英文翻译都是 B-Tree，这里的“-”并不是相对 B+ 树中的“+”，而只是一个连接符。这个很容易误解，所以我强调下。

而 B 树实际上是低级版的 B+ 树，或者说 B+ 树是 B 树的改进版。B 树跟 B+ 树的不同点主要集中在这几个地方：

*  B+ 树中的节点不存储数据，只是索引，而 B 树中的节点存储数据；
 *  B 树中的叶子节点并不需要链表来串联。

> 思考

1、B+ 树中，将叶子节点串起来的链表，是单链表还是双向链表？为什么？

双向链表

2、我们对平衡二叉查找树进行改造，将叶子节点串在链表中，就支持了按照区间来查找数据。散列表也经常跟链表一块使用，如果我们把散列表中的结点，也用链表串起来，能否支持按照区间查找数据呢？

散列表中的结点，用链表串联起来，支持按照区间查找数据的

--------------------

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

> 为什么需要索引？

*  “存储”需要的就是数据结构
 *  “计算”需要的就是算法
 *  “效率”就是索引

> 索引的需求定义

1、功能性需求

*  数据是格式化数据还是非格式化数据？
 *  数据是静态数据还是动态数据？
 *  索引存储在内存还是硬盘？
 *  单值查找还是区间查找？
 *  单关键词查找还是多关键词组合查找？

2、非功能性需求

*  不管是存储在内存中还是磁盘中，索引对存储空间的消耗不能过大。
 *  在考虑索引查询效率的同时，我们还要考虑索引的维护成本。

> 构建索引常用的数据结构有哪些？

*  **散列表**增删改查操作的性能非常好，时间复杂度是 O(1)。比如 **Redis、Memcache**，就是使用散列表来构建索引的。这类索引，一般都构建在**内存**中。
 *  **红黑树**作为一种常用的平衡二叉查找树，数据插入、删除、查找的时间复杂度是 O(logn)，也非常适合用来构建**内存索引**。**Ext 文件系统**中，对磁盘块的索引，用的就是红黑树。
 *  **B+ 树**比起红黑树来说，更加适合构建存储在**磁盘中的索引**。B+ 树是一个多叉树，所以，对相同个数的数据构建索引，B+ 树的高度要低于红黑树。当借助索引查询数据的时候，读取 B+ 树索引，需要的磁盘 IO 次数非常更少。所以，大部分关系型数据库的索引，比如 **MySQL、Oracle**，都是用 B+ 树来实现的。
 *  **跳表**也支持快速添加、删除、查找数据。而且，我们通过灵活调整索引结点个数和数据个数之间的比例，可以很好地平衡索引对内存的消耗及其查询效率。**Redis 中的有序集合**，就是用跳表来构建的。
 *  **布隆过滤器**有一定的判错率。但是，我们可以规避它的短处，发挥它的长处。尽管对于判定存在的数据，有可能并不存在，但是**对于判定不存在的数据，那肯定就不存在**。而且，布隆过滤器还有一个更大的特点，那就是**内存占用非常少**。我们可以针对数据，构建一个布隆过滤器，并且存储在内存中。当要查询数据的时候，我们可以先通过布隆过滤器，判定是否存在。如果通过布隆过滤器判定数据不存在，那我们就没有必要读取磁盘中的索引了。对于数据不存在的情况，数据查询就更加快速了。
 *  **有序数组**也可以被作为索引。如果**数据是静态的**，也就是不会有插入、删除、更新操作，那我们可以把数据的关键词（查询用的）抽取出来，组织成有序数组，然后利用**二分查找**算法来快速查找数据。

> 思考

你知道基础系统、中间件、开源软件等系统中，有哪些用到了索引吗？这些系统的索引是如何实现的呢？

[18413c6597c2850b75367393b401ad60.jpg]: /images/20220301/17649f9443f6485c8510c9b29a850ff2.png
[4094a733986073fedb6b9d03f877d71e.jpg]: /images/20220301/47ed2c1e893f46d8971ab51c658bc070.png
[50f89510ad1f7570791dd12f4e9adeb4.jpg]: /images/20220301/1eb2a0c561024a149bf6ecd3826066ee.png
[dd9f5a4525f5029a8339c89ad1c8159b.jpg]: /images/20220301/ae82c7af608a4f5f872dbbc900ad4c12.png
[903ee0dcb62bce2f5b47819541f9069a.jpg]: /images/20220301/6c7dba111cfd41aba70193200e401cfa.png
[7e6ecc308fe44120f30de809822215ed.jpg]: /images/20220301/b391af03f9ff4e72ae2f33d48620d0bd.png
[0e37e597737012593a93105ebbf4591e.jpg]: /images/20220301/cd96417a9930416baab6d5493c99f377.png
[603cf91f54b5db21bd02c6c5678ecf40.jpg]: /images/20220301/16cdc07e33c1424a8bc0b82050a4c8c9.png
[4480a314f9d83c343b8adbb28b6782ad.jpg]: /images/20220301/3e8573b757724995a53f191337f0bb44.png
[04650d9470b1e67899f5b8b7b8e33212.jpg]: /images/20220301/ea0a82b9955f47dda50d0d15e2dd8dc5.png
[a6c4c347b7cbdf57662bab399ed36cc3.jpg]: /images/20220301/40680bd9d628425283f430d8694700a2.png
[48e3bd2cdd66cb635f8a4df8fb8fd64e.jpg]: /images/20220301/e45e8aefae324ac98cfd742613fb6672.png
[b93c1fa4de16aee5482424ddf49f3c29.jpg]: /images/20220301/c4a1e76cd56a4b4888a25bb82b44705a.png
[ac76d78c064a2486e2a5b4c4903acb91.jpg]: /images/20220301/73c5d648650345edb61f3fb91dbb5c68.png
[eca118d673c607eb2b103f3476fb24ec.jpg]: /images/20220301/94a66ae720e04b84a029ecc59f63b033.png
[44075213100edd70315e1492422c92af.jpg]: /images/20220301/d8f1ef72b4c84a0c9e7a80cf2ff3db0b.png
[5f73f61bf77a7f2bb75f168cf432ec44.jpg]: /images/20220301/77e2f8230f2c4f59b583b73b0e71390d.png
[492206afe5e2fef9f683c7cff83afa65.jpg]: /images/20220301/b015f589eb5849bf84c7c8b7137d033f.png
[25700c1dc28ce094eed3ffac394531f4.jpg]: /images/20220301/57e68057831745ce9ff2788ffe9482cc.png
[1cf179c03c702a6ef5b9336f5b1eaecc.jpg]: /images/20220301/275c6eb0bd04423fa3996081a3dc2cd3.png
[69d4c48c1257dcb7dd6077d961b86259.jpg]: /images/20220301/5d8d5a71dd2d497082ec1db7012c2366.png
[ea4472fd7bb7fa948532c8c8ba334430.jpg]: /images/20220301/49da4ab0763c4cb1a768ea0615c189e5.png
[1800bc80e1e05b32a042ff6873e6c2e0.jpg]: /images/20220301/391d95f6555f42c1ab3d20e5db5368e4.png
[1730e34450dad29f062e76536622c918.jpg]: /images/20220301/56bc132fb84546f0a11eac15087d42e6.png