Some Questions About B+ Trees and Skip Lists

Translated
1

Note:
This topic has been translated from a Chinese forum by GPT and might contain errors.

Original topic: 关于B+树和跳表的一些疑问

| username: ryans

Speaking of which, MySQL uses B+ trees, while TiKV uses skip lists because its underlying storage is RocksDB.

So, if TiDB were not constrained by the underlying storage, would it prefer B+ trees or skip lists?

I’ve seen discussions about MySQL, saying that skip lists are not suitable for queries because of their high levels. But if we change the probability to reduce the number of levels or limit the maximum number of levels, what would be the difference compared to B+ trees?

I feel that the stability might not be as good as B+ trees, but in other aspects, these two are essentially the same.

2
| username: xfworld | Original post link

Check out TiFlash and TiKV 6.1 engine

There has been a recent interpretation, I suggest you take a look.