我一直看到一些文章提到memtables通常是由一个自平衡树支持的，比如AVL树或红黑树。
示例：
- https://www.linkedin.com/pulse/data-structures-powering-our-database-part-2-saurav-prateek?trk=pulse-article_more-articles_related-content-card
- https://medium.com/codex/understanding-log-structured-merge-lsm-trees-c4a0039f17a8
如果你真的看看Cassandra或rocksDB的实现，它们都使用跳过列表作为底层数据结构。我认为这是因为树的并发支持很差，因为由于自平衡属性，在写入时需要锁定许多节点。
如果是这样的话，为什么在讨论memtables的时候，有那么多的文章提到树而不是跳表呢？我错过什么了吗？
1条答案
按热度按时间kuarbcqp1#
据我所知，Cassandra使用一个跳表来索引memtable中的分区，然后使用b树来索引每个分区中的行，但这是最新的实现。如果你想深入了解一些最近的memtable实现，我推荐我的同事Branimir的文章，他在这个问题上比我更有知识：https://www.vldb.org/pvldb/vol15/p3359-lambov.pdf