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

1次阅读

共计 234 个字符,预计需要花费 1 分钟才能阅读完成。

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

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

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

正文完
 0