有没有熟悉B+树的朋友?

C 9月前 3904

想咨询一下,从没见过B+树每个节点都精准记录子节点数量的解决方案。

如果记录了,不是可以更快速地解决分页问题,和offset指定数量查询吗?

不记录子节点数量,导致这样设计的原因有哪些?

别问OpenAI了,它听不懂。

最新回复 (8)
  • C 9月前
    2

    B+树的设计目标是优化数据库索引的性能,尤其是在磁盘I/O方面。虽然记录子节点数量可以在某些情况下提供更快速的分页计算,但这样做会引入其他问题。

    让我们探讨一下:

    记录子节点数量的优点:

    如果每个内部结点都记录了子节点的数量,那么在进行分页查询时,可以更快速地计算出偏移量(offset)。

    例如,如果我们要获取第100页的数据,我们可以通过累加每个内部结点的子节点数量来找到正确的叶子结点,而无需遍历整个树。

    问题和权衡:

    记录子节点数量会增加每个结点的存储空间。这可能导致树的高度增加,进而增加磁盘I/O次数。

    此外,更新操作(如插入和删除)会变得更加复杂,因为每次修改子节点数量时都需要更新父节点。

    B+树的现有解决方案:

    B+树通常不记录子节点数量,而是通过叶子结点之间的链接来遍历数据。

    叶子结点的P_next指针可以帮助快速访问磁盘记录,效率非常高。

    对于分页查询,B+树可以使用类似二分查找的方式来定位叶子结点,然后再遍历叶子结点中的数据。

    解决方案:

    如果您需要更快速的 offset 计算,您可以考虑自定义一种 B+ 树变体,其中记录了子节点数量。这样可以在某些特定场景下提高分页计算的速度。

    但是请注意,这样的变体需要权衡存储空间和更新操作的复杂性。您需要根据具体的应用场景来决定是否值得引入这样的改进。

    总之,传统 B+ 树虽然不直接记录子节点数量,但其设计经过权衡,旨在最大程度地优化数据库索引的性能。如果您有特定的需求,可以考虑自定义变体来满足您的需求。

  • C 9月前
    3

    GPT给的答案看起来合理,不过下定义的车轱辘话来回说。

    现在的市场应用对分页的计算需求非常大,为何要舍弃掉呢……

  • v2016 9月前
    4

    b+树做范围查询效率要高,每个叶子结点存的有下一个的指针

  • heheking 9月前
    5

    gpt 说的没毛病,我也觉得这个方案不太可取,理由是读性能的提升大概率不足以弥补写性能的消耗;

    只读不写的情况下,你说的记录 offset 的方式确实可以加速查询,但是类似的场景更适合采用类似将热点数据缓存之类的方案;

    常规场景下,如果每一个节点都记录了一个子节点数,索引的更新时需要连同该量一起更新,读写产生了额外的开销,我认为这是有违 b + 树设计初衷的;

    PS:只考虑列表分页的场景,为什么不用 es 呢?

  • C 9月前
    6
    v2016 b+树做范围查询效率要高,每个叶子结点存的有下一个的指针

    做范围查询、链表查询都可以走叶子结点的左右指针。但是不知道范围起始点的前提下,比如我要查询第10万-10万+100条数据,它就需要从头遍历叶子节点,效率就没那么高了。

  • C 9月前
    7
    heheking gpt 说的没毛病,我也觉得这个方案不太可取,理由是读性能的提升大概率不足以弥补写性能的消耗; 只读不写的情况下,你说的记录 offset 的方式确实可以加速查询,但是类似的场景更适合采用类似将热点 ...

    我做的比这个复杂些,是对数据进行均匀切分,多线程/多节点做同步运算。

    模式就类似于分页了,不过每段(每页)的数据可能多达几万个。

    在总数据量非常大的情况下,想实现这个功能,就需要严谨的统计和拆分了。

  • heheking 9月前
    8
    C 我做的比这个复杂些,是对数据进行均匀切分,多线程/多节点做同步运算。 模式就类似于分页了,不过每段(每页)的数据可能多达几万个。 在总数据量非常大的情况下,想实现这个功能,就需要严谨的统计和拆分了 ...

    感觉有点既要又要了。。。不适合再继续往数据库方向深究,至少关系型数据库满足不了的吧?

    没法只讨论数据结构,你都多线程多节点同步了,又要从零考虑调度、通信啥的一堆问题巴拉巴拉~

    不对,肯定是设计方向有问题,百万行数据分页的需求,堆硬件提升更快,很难想象是什么具体的场景需要考虑这些东西

  • C 9月前
    9
    heheking 感觉有点既要又要了。。。不适合再继续往数据库方向深究,至少关系型数据库满足不了的吧? 没法只讨论数据结构,你都多线程多节点同步了,又要从零考虑调度、通信啥的一堆问题巴拉巴拉~ 不对,肯定是设计方向 ...

    也没那么复杂....多节点是以后想的事情了,当下就是在同一个数据库发起多个读取线程,每个线程读取数据的不同分段,然后各自执行各自的查询。目前的B+tree模式只能从头一个个读取,没有分段后多线程执行速度快。

    • 屌丝论坛
      10