database - 如何在键/值存储之上构建数据库索引？

Question

我正在阅读有关LevelDB并发现：

即将发布的 Chrome 浏览器版本包括 IndexedDB HTML5 API 的实现，该 API 构建在 LevelDB 之上

IndexedDB也是一个简单的键/值存储，具有索引数据的能力。

我的问题是：如何在键/值存储之上构建索引？我知道索引的最低级别是 n-ary 树，并且我了解数据在数据库中的索引方式。但是如何使用像 LevelDB 这样的键/值存储来创建数据库索引呢？

Answer 1

重要的特性不是它支持自定义比较器，而是它支持通过键的有序迭代，从而搜索部分键。您可以仅使用分隔字符串值的约定来模拟键中的字段。位于 leveldb 之上的许多脚本层都使用这种方法。

键值存储的字典视图是，您只能通过完全匹配来判断键是否存在。仅仅使用这样的 KV 存储作为数据库索引的基础是不可行的。

只要您可以从部分匹配开始遍历键，您就有足够的能力为索引提供搜索和排序操作。

Answer 2

只是几件事，LevelDB 支持使用自定义比较器对您链接到的页面中的数据进行排序：

根据项目现场，主要特点是：

• 键和值是任意字节数组。
• 数据按key排序存储。
• 调用者可以提供自定义比较函数来覆盖排序顺序。
• ……

所以 LevelDB 可以包含可以根据 1 个排序顺序排序/索引的数据。

如果你需要几个可索引的字段，你可以添加你自己的在 LevelDB 之上工作的 B-Tree。我想这是 Chrome 浏览器采用的方法类型，但我只是猜测。

您可以随时浏览 Chrome 源代码。