关于#结点#的问题，如何解决？

img

img

对于B选项，前驱结点应该是前一位，如果它的左子树再长一点的话，最右结点就排不到根节点的前面了。那为什么B是正确的

这个选项问的是前驱节点哦，肯定是当前节点的左子树全部遍历之后才到当前节点的对不，然后左子树的最后一个点不就是最右下节点了
如果是一直延申没有右子树的话，那当前节点的左子树的根就是最右节点

看完这篇博客，你就懂了：https://blog.csdn.net/weixin_45863060/article/details/116982736

不知道你这个问题是否已经解决, 如果还没有解决的话:
  • 这有个类似的问题, 你可以参考下: https://ask.csdn.net/questions/7587392
  • 这篇博客你也可以参考下：B树、B树的特性及B树在磁盘文件中的应用
  • 除此之外, 这篇博客: 深入理解数据库索引的实现原理中的 首先第一个问题：为什么不使用红黑树，而是使用B树？ 部分也许能够解决你的问题, 你可以仔细阅读以下内容或者直接跳转源博客中阅读:

    原因在于B树能够充分利用磁盘预读原理，而红黑树由于逻辑上很近的节点，物理上可能很远，无法利用局部性，导致效率比B树差很多。我们来了解一下什么是局部性原理和磁盘预读原理

    局部性原理与磁盘预读：

由于存储介质的特性，磁盘本身存取就比主存慢很多，再加上机械运动耗费，
磁盘的存取速度往往是主存的几百分分之一，因此为了提高效率，
要尽量减少磁盘I/O。为了达到这个目的，磁盘往往不是严格按需读取，
而是每次都会预读，即使只需要一个字节，磁盘也会从这个位置开始，
顺序向后读取一定长度的数据放入内存。这样做的理论依据是计算机科学中著名的局部性原理： 
当一个数据被用到时，其附近的数据也通常会马上被使用。 
程序运行期间所需要的数据通常比较集中。 
由于磁盘顺序读取的效率很高（不需要寻道时间，只需很少的旋转时间），因此对于具有局部性的程序来说，预读可以提高I/O效率。

    我们来分析一下B树的性能效率

    假设B树的高度为h,B树一次检索最多需要h - 1次I/O(因为根节点常驻在内存中)。

    h =   

    但数据库系统巧妙利用了磁盘预读原理后，将一个节点的大小设为等于一个页。B树新建一个节点时，直接申请一个页的空间，这样就保证一个节点物理上也存储在一个页里，加之计算机存储分配都是按页对齐的，就实现了一个节点只需一次I/O。

    渐进复杂度变为O（h）= 

    ,一般实际应用中，出度d是非常大的，通常超过100，因此h非常小（通常不超过3），三层的B树可以存放上百万数据。也就是说，最多需要2次I/O就可以查找目标数，性能可见极其强悍！

    而红黑树由于逻辑上很近的节点，物理上可能很远，无法利用局部性，其渐进复杂度也为之前的O（h）。效率与B树无法比较。

  • 您还可以看一下 刘国柱老师的热更新框架设计之客户端热更框架(中部)视频课程课程中的 重定义热更路径工具类(B)小节, 巩固相关知识点

如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^