02 | 非线性结构检索：数据频繁变化的情况下，如何高效检索？
讲述：陈东
时长18:55大小17.33M
树结构是如何进行二分查找的？
二叉检索树的检索空间平衡方案
跳表是如何进行二分查找的？
跳表的检索空间平衡方案
重点回顾
课堂讨论
精选留言(17)
2020-03-251，虽然时间复杂度一致，但并不代表真实的时间一致，时间复杂度只是量级，所以数据量小的情况下，数组能甩其他结构几条街。2，就是存储空间的节省。
这篇文章让我有很多延伸想法，1，检索操作映射到底层核心就是cpu对存储的寻址方式，而这上层的抽象就是指针和数组，老师向我们展示了添加指针构建二叉树的过程，反过来思考，每个数据项都有对其他数据项的指针，检索问题就变成了留下那些对检索有帮助的指针，可以是比自身大的，可以是和自身相等的。而数组我把它抽象成这样一种结构，即我有一个中心节点知道指向所有数据的指针，而且还知道哪个指针指向的是第几个元素，只不过这里的指针是隐含的。
2 最近一直在想 计算机工程是tradeoff 的艺术，但我感觉大部分人很容易就变成了定性的说这个是时间换空间，这个是低延时是靠降低吞吐来换取的，但这个完全就是纸上的意淫，没有定量的思考就是耍流氓，就好像数组虽然我们说加个元素会导致大量元素迁移，你知道这个迁移的代价是多少吗，就是迁移的数据的个数吗，单位是多少呢？ 当然定量又是何其艰难，业务何其复杂，计算机层次又何其多。展开作者回复: 你的思考有两点非常好！
一个是从实际实现出发，而不是停留在纸面分析。由于有内存局部性原理，数组的查询效率是高于树和跳表的。甚至在小数据的情况下，都有可能数组的移动代价也不高（可用内存拷贝）。还有，数组还有范围查找能力更强的特点。
而另一点，你很好地去开始思考和抽象事情的核心，这是构建自己知识体系的很好的实践。 10
2020-03-25跳表并不能完全替代有序数组
1.有序数据占用的内存空间小于调表
2.有序数组的读取操作能保持在很稳定的时间复杂度，而调表并不能
3.因为数组存储空间是连续的，可以利用内存的局部性原理加快查询
Redis 为何采用跳表而不是红黑树？
1.跳表比红黑树更简单的实现了检索空间的平衡
2.跳表保持了链表顺序遍历的能力，需要遍历的场景，跳表比红黑树用起来方便展开 5
2020-03-25有序数组 使用的是一段连续的内存可以支持随机访问，而且由于使用的是连续的内存的 可以高效使用 CPU 的局部性原理，可以缓存要访问数据之后的数据，进而范围查询更高效作者回复: 总结得很好
4
2020-03-25随机访问，充分利用CPU缓存，节省内存展开作者回复: 回答很简明扼要！
除此之外，还有范围查找效率更高（CPU缓存 + 内存拷贝） 4
2020-03-29这个算法层层引入挺好，学习方法展开作者回复: 这个也是我专栏设计的目标之一。用前面的知识引出后面的知识。后面的知识是前面的知识的灵活应用。
课程用到的知识基本都是自成体系，这样大家在学习的时候就不用再去其他地方补基础知识了。 2
2020-03-25为了将 k 插入到跳表中，需要检索跳表以确定其插入位置，同时还要为其生成一个随机的层级。
如何确定插入位置？为何使用一个随机的层级？目前还没有头绪…展开作者回复: 1.确认k的插入位置 : 其实就是在跳表中查询“k”，如果不存在，那么最后的查询位置，就是k应该插入的位置；如果k已经存在（假设允许重复元素），那么就在找到的k的后面插入。
2.随机的层级，是用概率的思路来解决跳表指针平衡分布的问题。我可以换一种角度再描述一下。你可以按我的描述，在纸上将图画出来，看看是否会好理解:
假设我们有m个节点，由于随机函数是（1/2）^n，因此，每个节点有第0层的概率是1，也就是说，所有的节点都有一个指向下一个节点的指针。（试着画出来）
而节点拥有第1层的概率，变成了1/2，也就是只有一半的随机节点会有第1层，那么这一半的节点就会连起来。（试着画出来）
在这一半的节点中，拥有第3层的节点数，又是随机的一半。（试着画出来）
你会看到，通过一个简单的随机函数，就能完成跳表的平衡分布指针的目的。 2
2020-03-25最主要还是以空间换时间吧！
还有就是要考虑业务场景，如果存储的对象本身没有多大，却存了一大堆地址，是得不偿失的。展开作者回复: 是的。合理的空间利用率也是很重要的事情。
此外，由于有内存局部性原理，因此，连续空间上的查询性能实际上会比树和跳表好 2- 2020-03-25在小数据量、修改不频繁的场景下，有序数组可以获得稳定的且较短的查询时间，但调表由于新插入元素的指针间隔并不均匀，所以查询时间就得不到很好的保证展开
作者回复: 是的，小数据量下，数组会有更稳定的性能。
但不仅如此，由于内存局部性原理，大数据量下，数组的查询效率依然很高。
此外，对于范围查找，数组也有更高的效率（内存局部性原理+内存拷贝） 2 - 2020-03-25跳表并不能完全替代有序数组
1.有序数据占用的内存空间小于调表
2.有序数组的读取操作能保持在很稳定的时间复杂度，而调表并不能
3.因为数组存储空间是连续的，可以利用内存的局部性原理加快查询展开作者回复: 在内存空间之外，你说到了很重要的两点:
1.小数据范围下，跳表性能没有数组稳定。
2.考虑内存局部性原理，数组实际查询效率更高。
此外还有一点，考虑到范围查找需求，数据的处理效率会更高（内存拷贝+内存局部性原理） 2 
2020-03-25只想到一个节约内存空间展开作者回复: 节约空间的确是最大的一个优点。很多时候，内存空间是紧张的，甚至需要我们做数据压缩处理。在这种场景下，如果适合用数组，就不应该用树或者跳表。
此外，尽管理论上时间代价级别相同，但由于有内存局部性原理，连续空间的数据被处理的效率会更高。因此数组的实际查询效率会更高。
并且，如果考虑范围查找，数组能快速处理大段区域（比如使用内存拷贝技术），再叠加局部性原理，范围查找数组效率会远高于跳表和树。 1 2
2020-03-30对数组、链表、跳表、树的搜索有了进一步认识。谢谢老师！作者回复: 继续加油！
1
2020-03-29老师说RandonLevel的结果是随机的，如果说RandomLevel的结果没有范围的话，那next数组的大小不就没法确定了吗？展开作者回复: 其实可以使用可变长数组来处理。一种简单的可变长数组实现方案就是:先给数组一个固定的初始长度，如果数组写满了，就生成一个原数组两倍大小的新数组，然后将原数组的元素都导入新数组中。
关于可变长数组，你可以参考一下c++中vector的实现方案。 1
2020-03-28在读少写多的场景下，需要频繁变更以使得数据有序，是不是就不会考虑用数组，而是优先考虑二叉树和跳表作者回复: 如果频繁修改的代价很大，影响到了整体性能，那么的确二叉树和跳表表现会更好。
当然，如果数据规模不大的情况下，数组性能有内存局部性原理的加持，即使是频繁插入和删除，也不一定性能很差。因此要合理评估。 1
2020-03-27数组有自己的独特优势，比如数据集中存放的，程序在从内存到缓存取数据的时候，一次性搬一块数据，临近的数据都搬进来了，而二叉树和调表，用指针连接，无法利用缓存局部性原理的优势；虽然数组插入和删除性能差，当时有的场景并不需要这些，有的只需要构建好就不变了，这种比较适合用数组。展开作者回复: 是的。数组的内存局部性优势是很重要的一点。甚至对于小规模数据集来说，插入删除时大块移动数据的性能也不见得差。
1- 2020-03-26对于图中的插入节点k，听了老师的讲解也明白了，但是在思考具体的实现的时候，不知道如何下手，对于图中的单链表而言，插入节点k需要修改两层的指针连接，那它不就需要两个pre指针，分别指向a5, a6;那如果要插入的节点位于a4和a5之间而且RandomLevel的结果为3的话，岂不是需要3个pre指针；昨晚想了好久也没想出来应该如何实现插入，今天我在总结向老师提问的时候突然想到是不是跳表在设计的时候每一层都有一个指针呢？
还有一个问题就是对于二叉搜索树而言，如果插入的节点重复了怎么办呢？因为我觉得这个问题虽然在例子中很好解决，如果重复的话，直接放弃插入就是了，但是对于真实的场景又该如何解决呢？希望老师解答。展开作者回复: 动手实践是非常棒的！尤其是我的专栏重点是在检索原理和分析上，因此如果你能自己去学习细节，这就是非常好的补充。接下来，我来给你补充一下细节:
1.跳表本身已经有了许多指针，因此如果用双链表的方式实现的话，指针数会翻倍。不合适。因此，跳表是单向的，没有pre指针。
2.对于单链表的插入，我们的具体实现是给单链表加上一个头节点，然后寻找插入位置的“pre节点”来完成操作。跳表也是一样，有一个头节点。头节点的level，是所以节点中level的最大值。从头节点开始，每个level的指针链接，可以看做多个独立的单链表。（你可以画出来看看）
3.插入新节点的时候，核心思路是“寻找每个level的pre节点”。以我文章中插入k的例子来说，我们是怎么寻找到它的插入位置的？我们是先用第2层的指针进行遍历，发现k应该在a5到a9之间。于是，k的第2层的pre节点是a5！把a5记下来！（pre_node[2]=a5；）
然后，接下来，我们会用第1层的指针去遍历，这时候，会发现k在a5和a7之间。于是，k的第1层的pre节点是a5！！（pre_node[1]=a5；）
最后，用第0层的指针遍历，发现k在a6和a7之间，于是，k的第0层的pre节点是a6！！（pre_node[0]=a6；）
下一步，就把每一层的pre node和k的对应层连起来就好了。
4.一个有意思的场景，k有小概率生成4层指针，甚至5层指针，如果超出了之前所有节点的level，那么头节点就会扩展自己的level，低层level处理不变。新增的高层level直接连到k上。你会发现，随机level这个方法，完全基于概率，不用去考虑当前跳表中有多少个节点，这也是很巧妙的一点。
第二个问题:二叉检索树如何处理重复节点?如果你注意看我原文，我写了“右子树所有节点的值都大于等于根节点”。因此，二叉检索树是允许插入重复节点的。它的插入逻辑是“放在以该节点为根，右子树的最左节点的位置”。其实所谓“右子树的最左节点的位置”，其实拉直成链表来看，就是紧邻这个元素的后一个位置。 1 - 2020-03-25我在学习红黑树的时候，深知红黑树的复杂，即使后来阅读《算法4》通过2-3树的方式来写红黑树，其实还是很有难度的，跳表在本身实现简单的情况下拥有和红黑树同等级别的性能，虽然应用没有红黑树广泛，但是确实是一个极其精巧的数据结构。展开
作者回复: 是的。所以跳表的设计很精巧。而且这种随机搭建高速通路的思路，在一些图搜索的场景中也有借鉴。
1 - 2020-03-25有序数组优势是:一，快速而稳定的读性能，时间复杂度永远是O（1）.二，不会导致内存碎片化，避免了内存浪费.展开
作者回复: 数组的确比跳表更加稳定。不过内存碎片化问题，这个会有内存碎片处理来解决。
其实，还有两点是很关键的，一个是考虑实际情况，内存有局部性原理，对连续空间的处理会更高效；另一个是考虑范围查找，数组将查询结果成片复制出来效率会更高（内存拷贝技术+内存局部性原理） 1
