database - 数据库如何实现跳过？

Question

我正在编写自己的小型数据库引擎。除了检查 B+tree 的每个叶节点之外，是否有任何有效的方法来实现跳过功能，这对于大条目来说会很慢。

Answer 1

如果您使用 B+tree 作为索引，则所有值都存储在叶子中，因此可以链接在一起以形成（有序）链表，或者更确切地说是展开的链表。这是 B+ 树相对于普通 B 树的主要优势。

也就是说，即使展开列表允许您执行某种形式的跳过，也没有什么能阻止您在记录上实现跳过列表，并将这些列表的节点用作您的 btree 值。

Answer 2

2年后，但无论如何。你也可以用 Cassandra 的方式来做。没有限制，但您指定上一个查询的最后一个键，例如

select * from abc where key > 123 limit 100

其中 123 是上一个查询的最后一个键