V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
hackingwu
V2EX  ›  程序员

二叉树存储磁盘为什么要一页存一层节点的数据呢

  •  
  •   hackingwu ·
    hackingwu · 2022-10-30 12:24:23 +08:00 · 1733 次点击
    这是一个创建于 753 天前的主题,其中的信息可能已经有所发展或是发生改变。

    二叉平衡树——>B Tree 是为了解决查询多层数据要多次 IO 的问题。 因为二叉树在存储到磁盘后,是一层存在一页。为了减少 IO ,所以要减少树的高度。 那我有一个问题?为什么要一页存一层节点的数据,不能一页存多层呢? 是为了预留空间修改节点数据内容吗?

    8 条回复    2022-10-30 21:16:59 +08:00
    Jooooooooo
        1
    Jooooooooo  
       2022-10-30 13:24:54 +08:00
    哪里看的...

    二叉树只是一种结构而已, 和存储是无关的.
    hackingwu
        2
    hackingwu  
    OP
       2022-10-30 13:25:25 +08:00
    @Jooooooooo 那存到磁盘怎么存呢?
    liuxu
        3
    liuxu  
       2022-10-30 15:51:11 +08:00
    加入于 2013-11-12 ,既然是上了年纪的老大哥,这个问题就要慎重对待了

    这里的页我就作为磁盘的 block 说了

    如果需要把内存中 B tree 数据结构存储到磁盘中,1 个页存储 1 层,或多页存储 1 层是最合理的
    如果存储多层,假如 2 层和 3 层存储在一个页中,此时如果 2 层还增加 1 个节点,就必须把 3 层移到别的页中,然后在 2 层的页中插入,这就是 mysql/innodb 中常说的“页分裂”问题
    stein42
        4
    stein42  
       2022-10-30 16:26:20 +08:00
    如果用磁盘页来存储二叉树节点:
    1 页存 1 层,最多 1 个 key-value ,2 个孩子,非常浪费空间。
    1 页存 2 层,最多 3 个 key-value ,4 个孩子。
    1 页存 3 层,最多 7 个 key-value ,8 个孩子。
    ...
    1 页存 n 层,最多 2^n-1 个 key-value ,2^n 个孩子。
    选择适当的 n ,使得空间刚好利用完。

    这样的结构,再改进一下插入、删除操作,就得到了 B 树。
    hhjswf
        5
    hhjswf  
       2022-10-30 17:57:20 +08:00 via Android
    你怎么不问,为啥不把所有节点都存在一个内存块
    saberlong
        6
    saberlong  
       2022-10-30 20:32:05 +08:00 via Android
    综合实现复杂度,节点检索性能等等的考虑吧。
    1.一页一个节点。页的地址即可表示节点,那么可以直接根据页号找到对应节点数据。如果一页多节点还得额外存信息来索引节点所在位置,并且存取和更新都会有额外的复杂度,提高开发难度,对性能不友好。
    2.一个节点可能跨页。当 key 或 value 数据过大时,需要跨页。至于跨页的分配管理得看实现。我以前写的是和节点页采用同一套页管理,加个特殊标识。而像 etcd 的底层 bbolt 是采用相邻连续页组合成一个页,这样开发复杂度降低,感觉空间浪费会多些。
    xilou31
        7
    xilou31  
       2022-10-30 21:14:52 +08:00
    页的概念,本身就是一个有序的双向链表。

    如果一页存多层,就不能用二分法进行节点的查找了,效率反而降低。
    xilou31
        8
    xilou31  
       2022-10-30 21:16:59 +08:00
    #7 好像也不太对,双向链表不能用二分法
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1030 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 23ms · UTC 19:32 · PVG 03:32 · LAX 11:32 · JFK 14:32
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.