skiplist 作为常用于 LevelDB,RocksDB 中的数据结构，在每次插入新数据时，会生成随机的层高。
如果每次创建新 skiplist 时，都使用完全相同的随机函数以及 seed ，从而每个 skiplist 被填满后，其层高的布局皆相同，这样相比于每次都完全随机层高的布局，会否降低查询效率？写入又会否有所改善，因为仅需查表而非摇色子。
想法是，写入数据的顺序本身就是随机的，被复用的层高布局本身也是随机的，只是从宏观看，所创建的所有 skiplist 实例的层高布局不够随机。
1 条回复 • 2024-09-03 18:19:50 +08:00
 |
1
MoYi123 22 天前
查表你还要额外内存呢, 用 seed 产生随机数不比查表好?
|
Select Language