c# - 如何在数据库中存储稀疏 bool 向量？

Question

假设我有一本书有 ~2^40 页。每天，我都会随机阅读一大块连续的页面(有时包括一些我已经阅读过的页面)。在 (SQLite) 数据库中存储和更新“我读过哪些页面”信息的最聪明的方法是什么？

我目前的想法是将 [firstChunkPage, lastChunkPage] 条目存储在一个表中，但我不确定如何有效地更新它。

• 我应该先检查所有可能的重叠然后再更新吗？
• 我是否应该只插入我的新范围，然后合并重叠的条目(可能多次，因为可能会发生多次重叠？)？我不确定如何构建这样的 SQL 查询。

这看起来是一个很常见的问题，所以我想知道是否有人知道这个问题的“公认”解决方案。

欢迎任何帮助或想法!

编辑:读取实际上不是随机的， block 的数量预计将非常恒定并且与页面数量相比非常小。

Answer 1

如果数据相对稀疏，您存储 (firstChunkPage, lastChunkPage) 对范围的想法应该可行。

不幸的是，您提到的查询:

SELECT count(*) FROM table
WHERE firstChunkPage <= page AND page <= lastChunkPage

无法有效地工作，除非您使用空间索引。

对于 SQLite，你应该使用 R-Tree module ，它实现了对这种索引的支持。引用:

An R-Tree is a special index that is designed for doing range queries. R-Trees are most commonly used in geospatial systems where each entry is a rectangle with minimum and maximum X and Y coordinates. ... For example, suppose a database records the starting and ending times for a large number of events. A R-Tree is able to quickly find all events, for example, that were active at any time during a given time interval, or all events that started during a particular time interval, or all events that both started and ended within a given time interval.

使用 R-Tree，您可以在插入新范围并用新的组合条目替换它们之前非常快速地识别所有重叠。

要创建您的 RTree 索引，请使用如下内容:

CREATE VIRTUAL TABLE demo_index USING rtree(
    id, firstChunkPage, lastChunkPage
);

欲了解更多信息，read documentation .