I keep seeing articles that mention how memtables are usually backed by a self balancing tree like AVL tree or red-black tree.
Examples:
If you actually look at Cassandra or rocksDB implementation, they both use skip lists as the underlying data structure. I assume this is because trees have poor concurrency support since a lot of nodes would need to be locked when writing due to the self balancing property.
If this is the case, why are so many articles mentioning trees rather than skip lists when discussing memtables? Am I missing something?
As I understand it, Cassandra uses a skip list for indexing partitions in the memtable, and then b-trees to index the rows inside each partition, but that's the most recent implementation. If you want a deep dive on some of the more recent memtable implementation, I recommend my colleague Branimir's article, he is far more knowledgable than I on the subject: https://www.vldb.org/pvldb/vol15/p3359-lambov.pdf