02 | 非线性结构检索：数据频繁变化的情况下，如何高效检索？
该思维导图由 AI 生成，仅供参考
树结构是如何进行二分查找的？
荧光笔
直线
曲线- 深入了解
- 翻译
- 解释
- 总结
本文介绍了在非线性树状结构中提高检索效率的方法，主要包括二叉检索树和跳表两种数据结构。通过将有序链表改造为具有二分查找能力的二叉检索树，实现了快速检索。文章详细介绍了二叉检索树的构建过程，以及如何保持检索空间的平衡，确保检索效率。同时，还提到了跳表的实现原理和检索空间平衡方案。跳表通过随机生成节点层数的方式，保证了指针的分布在大概率上是平衡的，从而实现了检索空间的平衡。相比于复杂的平衡二叉检索树，跳表用一种更简单的方式实现了检索空间的平衡，并且在需要遍历功能的场景中更为方便。总的来说，本文通过讲解树状结构的二分查找原理和平衡性，为读者提供了在数据频繁变化情况下高效检索的技术思路。文章还提到了二叉检索树和跳表的查询时间代价和调整能力，以及与有序数组的比较，引发读者对这些数据结构的思考和讨论。
《检索技术核心 20 讲》，新⼈⾸单¥59
全部留言(35)
- 最新
- 精选
峰1，虽然时间复杂度一致，但并不代表真实的时间一致，时间复杂度只是量级，所以数据量小的情况下，数组能甩其他结构几条街。2，就是存储空间的节省。 这篇文章让我有很多延伸想法，1，检索操作映射到底层核心就是cpu对存储的寻址方式，而这上层的抽象就是指针和数组，老师向我们展示了添加指针构建二叉树的过程，反过来思考，每个数据项都有对其他数据项的指针，检索问题就变成了留下那些对检索有帮助的指针，可以是比自身大的，可以是和自身相等的。而数组我把它抽象成这样一种结构，即我有一个中心节点知道指向所有数据的指针，而且还知道哪个指针指向的是第几个元素，只不过这里的指针是隐含的。 2 最近一直在想 计算机工程是tradeoff 的艺术，但我感觉大部分人很容易就变成了定性的说这个是时间换空间，这个是低延时是靠降低吞吐来换取的，但这个完全就是纸上的意淫，没有定量的思考就是耍流氓，就好像数组虽然我们说加个元素会导致大量元素迁移，你知道这个迁移的代价是多少吗，就是迁移的数据的个数吗，单位是多少呢？ 当然定量又是何其艰难，业务何其复杂，计算机层次又何其多。作者回复: 你的思考有两点非常好！ 一个是从实际实现出发，而不是停留在纸面分析。由于有内存局部性原理，数组的查询效率是高于树和跳表的。甚至在小数据的情况下，都有可能数组的移动代价也不高（可用内存拷贝）。还有，数组还有范围查找能力更强的特点。 而另一点，你很好地去开始思考和抽象事情的核心，这是构建自己知识体系的很好的实践。
2020-03-25233
giteebravo
为了将 k 插入到跳表中，需要检索跳表以确定其插入位置，同时还要为其生成一个随机的层级。 如何确定插入位置？为何使用一个随机的层级？目前还没有头绪…作者回复: 1.确认k的插入位置 : 其实就是在跳表中查询“k”，如果不存在，那么最后的查询位置，就是k应该插入的位置；如果k已经存在（假设允许重复元素），那么就在找到的k的后面插入。 2.随机的层级，是用概率的思路来解决跳表指针平衡分布的问题。我可以换一种角度再描述一下。你可以按我的描述，在纸上将图画出来，看看是否会好理解: 假设我们有m个节点，由于随机函数是（1/2）^n，因此，每个节点有第0层的概率是1，也就是说，所有的节点都有一个指向下一个节点的指针。（试着画出来） 而节点拥有第1层的概率，变成了1/2，也就是只有一半的随机节点会有第1层，那么这一半的节点就会连起来。（试着画出来） 在这一半的节点中，拥有第3层的节点数，又是随机的一半。（试着画出来） 你会看到，通过一个简单的随机函数，就能完成跳表的平衡分布指针的目的。
2020-03-25220
老姜随机访问，充分利用CPU缓存，节省内存作者回复: 回答很简明扼要！ 除此之外，还有范围查找效率更高（CPU缓存 + 内存拷贝）
2020-03-2512
与你一起学算法对于图中的插入节点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这个方法，完全基于概率，不用去考虑当前跳表中有多少个节点，这也是很巧妙的一点。 第二个问题:二叉检索树如何处理重复节点?如果你注意看我原文，我写了“右子树所有节点的值都大于等于根节点”。因此，二叉检索树是允许插入重复节点的。它的插入逻辑是“放在以该节点为根，右子树的最左节点的位置”。其实所谓“右子树的最左节点的位置”，其实拉直成链表来看，就是紧邻这个元素的后一个位置。
2020-03-26310
奕有序数组 使用的是一段连续的内存可以支持随机访问，而且由于使用的是连续的内存的 可以高效使用 CPU 的局部性原理，可以缓存要访问数据之后的数据，进而范围查询更高效作者回复: 总结得很好
2020-03-2528
阿斯蒂芬老师讲：「当我们从实际问题出发，去思考每个数据结构的特点以及解决方案时，我们就会更好地理解一些高级数据结构和算法的来龙去脉，从而达到更深入地理解和吸收知识的目的」，非常受用。 谈谈自身对「高级」的看法。起初总觉得高级就是比数组和链表功能更为强大逻辑更为复杂的数据结构，随着知识的不断学习，发现这种看法虽然不能说是错误的，但也是不全面的。如今我理解的高级觉得其就是基于低级的一种组合。这种组合相当美妙，在仅看外部结构的情况下会觉得像庞然大物难以学习，但找到方法拆解后就会发现其实来去还是老师说的：不外乎数组于链表尔。 好比树这个结构，其本质上就是链表的思想，只是从单指针链表变成了多指针链表，就是最简单的树，然后如果再对其数据排列方式进行限制，就衍生出了更多复杂的树。树本身并不是一个“原子”的数据结构，其实树还能够用数组表示，更为美妙。 再讲高级算法，就想到Java中HashMap的键值对存储实现，为了解决冲突使用链表，后来考虑链表可能出现的严重性能退化，又增加了在一定阈值下转换成红黑树的策略。其实这种内部数据结构的“进化”或“退化”。 包括老师举例的跳表，可以看到，它像链表，但又不是只有单指针，且每个节点的指针数目可能都不一样，而且节点还有层的概念，层又像是数组，那么这样的结构特点究竟有什么好处，这样的数据结构主要用来解决什么问题，为什么要设计成这样才能达到目的。又是老师的灵魂拷问三部曲，思考这些觉得非常有趣。 综上我认为「高级」就是一种表现形式。根据实际的数据场景，数据特点，选择最合适的存储结构，灵活组合或扩展，提供最有效率的存取接口，这算不算是检索的核心呢。作者回复: 我觉得你写得非常棒！其实许多工程师可能会觉得“高级数据结构”很cool很难，或者总觉得要不停学一些新技术新架构非常累。但实际上，基础的理论和工具还是那些，只要真正吃透了，结合实际场景，再结合你的理解和思考，其实许多高级数据结构或技术都是顺其自然的事情。 这其实就像乐高积木，基础的模块其实就那么几种。但只要结合你的理解，运用你的想象力和创造力，就能搭出复杂的建筑。因此，我认为，真正掌握了这些基础模块和构建思想，才是一个工程师的核心竞争力。
2020-04-1027
pedro我在学习红黑树的时候，深知红黑树的复杂，即使后来阅读《算法4》通过2-3树的方式来写红黑树，其实还是很有难度的，跳表在本身实现简单的情况下拥有和红黑树同等级别的性能，虽然应用没有红黑树广泛，但是确实是一个极其精巧的数据结构。作者回复: 是的。所以跳表的设计很精巧。而且这种随机搭建高速通路的思路，在一些图搜索的场景中也有借鉴。
2020-03-2527- 大头爸爸讲得非常好啊。请问有什么应用场合是适用于红黑树但不适用于跳表的呢？
作者回复: 尽管理论上红黑树和跳表的检索时间代价是一个量级的，但在实际工程实现中，如果跳表不做优化，那么会有两个缺点: 1.检索性能不够稳定，最差时间代价是o(n)。因为跳表是依赖于大量链接的随机分布来提高检索性能的，但是随机分布的性能并不是最优的，在极端情况下还可能退化到o(n)。 2.内存占用率较高，因为一个节点要带有多个指针，这会带来更大的存储开销。 因此，如果我们的应用场景要求检索性能稳定，节省内存，并且没有遍历需求，插入频率也不高的话(红黑树频繁插入数据时，加锁代价会比跳表大)，那么使用红黑树更合适。
2020-06-106 
目光之诚最主要还是以空间换时间吧！ 还有就是要考虑业务场景，如果存储的对象本身没有多大，却存了一大堆地址，是得不偿失的。作者回复: 是的。合理的空间利用率也是很重要的事情。 此外，由于有内存局部性原理，因此，连续空间上的查询性能实际上会比树和跳表好
2020-03-254- 千里之行在小数据量、修改不频繁的场景下，有序数组可以获得稳定的且较短的查询时间，但调表由于新插入元素的指针间隔并不均匀，所以查询时间就得不到很好的保证
作者回复: 是的，小数据量下，数组会有更稳定的性能。 但不仅如此，由于内存局部性原理，大数据量下，数组的查询效率依然很高。 此外，对于范围查找，数组也有更高的效率（内存局部性原理+内存拷贝）
2020-03-253