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

skiplist 节点的随机层高布局可以复用吗?复用后会损失多少效率

  •  
  •   dacapoday · 90 天前 · 945 次点击
    这是一个创建于 90 天前的主题,其中的信息可能已经有所发展或是发生改变。

    skiplist 作为常用于 LevelDB,RocksDB 中的数据结构,在每次插入新数据时,会生成随机的层高。

    如果每次创建新 skiplist 时,都使用完全相同的随机函数以及 seed ,从而每个 skiplist 被填满后,其层高的布局皆相同,这样相比于每次都完全随机层高的布局,会否降低查询效率?写入又会否有所改善,因为仅需查表而非摇色子。

    想法是,写入数据的顺序本身就是随机的,被复用的层高布局本身也是随机的,只是从宏观看,所创建的所有 skiplist 实例的层高布局不够随机。

    1 条回复    2024-09-03 18:19:50 +08:00
    MoYi123
        1
    MoYi123  
       90 天前
    查表你还要额外内存呢, 用 seed 产生随机数不比查表好?
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   5548 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 20ms · UTC 05:58 · PVG 13:58 · LAX 21:58 · JFK 00:58
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.