Riy*_*lla 16 nosql index mongodb couchdb
语境
这个问题与 SQL 和 NoSQL 数据库系统中索引的低级实现细节有关。索引的实际结构（B+ 树、哈希、SSTable 等）是无关紧要的，因为该问题特别与存储在任何这些实现的单个节点内的键有关。
背景
在SQL（如MySQL的）和NoSQL（CouchDB的，MongoDB的，等等）数据库，如果您在列或数据的JSON文档字段建立索引，你实际上是导致数据库做的就是创建本质上所有的排序列表这些值以及与该值相关的记录所在的主数据文件中的文件偏移量。
（为简单起见，我可能会忽略特定实现的其他深奥细节）
简单的经典 SQL 示例
考虑一个标准 SQL 表，它有一个简单的 32 位 int 主键，我们将在其上创建索引，我们最终将在磁盘上得到一个整数键的索引，该索引已排序并与数据文件中的 64 位偏移量相关联，其中记录存在，例如：
id | offset
--------------
1 | 1375
2 | 1413
3 | 1786
索引中键的磁盘表示如下所示：
[4-bytes][8-bytes] --> 12 bytes for each indexed value
坚持使用文件系统和数据库系统优化磁盘 I/O 的标准经验法则，假设您将密钥存储在磁盘上的 4KB 块中，这意味着：
4096 bytes / 12 bytes per key = 341 keys per block
忽略索引的整体结构（B+ 树、哈希、排序列表等），我们一次将 341 个键的块读写到内存中，然后根据需要返回到磁盘。
示例查询
使用上一节中的信息，假设有一个查询“id=2”，经典的数据库索引查找如下：
问题设置...
好的，这里是问题出现的地方......
步骤#2 是最重要的部分，它允许这些查询在 O(logn) 时间内执行......信息必须被排序，但你必须能够以快速排序的方式遍历列表......更多具体来说，您必须能够随意跳转到明确定义的偏移量以读取该位置的索引键值。
在块中读取后，您必须能够立即跳转到第 170 个位置，读取键值并查看您要查找的是 GT 还是 LT 那个位置（等等......）
您能够像这样在块中跳转数据的唯一方法是，如果键值大小都是明确定义的，就像我们上面的示例（每个键 4 字节然后 8 字节）。
题
好的，所以这里是我陷入高效索引设计的地方......对于 SQL 数据库中的 varchar 列，或者更具体地说，文档数据库中的完全自由格式的字段，如 CouchDB 或 NoSQL，您想要索引的任何字段都可以是任何字段length你如何实现索引结构块内的键值？
例如，假设您在 CouchDB 中对 ID 使用顺序计数器，并且您正在索引推文……几个月后，您的值将从“1”变为“100,000,000,000”。
假设您在第 1 天在数据库上构建索引，当数据库中只有 4 条推文时，CouchDB 可能会尝试对索引块内的键值使用以下构造：
[1-byte][8-bytes] <-- 9 bytes
4096 / 9 = 455 keys per block
在某些时候这会中断，您需要可变数量的字节来将您的键值存储在索引中。
如果你决定索引一个真正可变长度的字段，比如“tweet_message”或其他东西，这一点就更加明显了。
由于键本身是完全可变长度的，并且数据库在创建和更新索引时无法智能地猜测某个“最大键大小”，这些键实际上是如何存储在代表这些数据库中索引段的块中的?
显然，如果您的键是可变大小的并且您读入了一个键块，那么您不仅不知道该块中实际有多少个键，而且您也不知道如何跳到列表的中间来执行二进制操作搜索他们。
这就是我被绊倒的地方。
使用经典 SQL 数据库中的静态类型字段（如 bool、int、char 等），我知道索引可以预先定义键长度并坚持下去......但在这个文档数据存储的世界中，我是困惑他们如何在磁盘上有效地建模这些数据，以便仍然可以在 O(logn) 时间内对其进行扫描，并希望在此处进行澄清。
如果需要任何说明，请告诉我！
更新（格雷格的回答）
请参阅我对 Greg 回答的评论。经过一周的研究，我认为他真的偶然发现了一个非常简单和高效的建议，即实践中非常容易实现和使用，同时在避免反序列化您不关心的关键值方面提供巨大的性能优势。
我研究了 3 个独立的 DBMS 实现（CouchDB、kivaloo 和 InnoDB），它们都通过在其执行环境（erlang/C）中搜索值之前将整个块反序列化为内部数据结构来处理这个问题。
这就是我认为 Greg 建议的绝妙之处；2048 的正常块大小通常有 50 个或更少的偏移量，导致需要读入的非常小的数字块。
更新（格雷格建议的潜在缺点）
为了最好地继续与我自己的对话，我意识到了以下缺点......
如果每个“块”都以偏移量数据开头，则您不能允许在稍后的配置中调整块大小，因为您最终可能会读取未以正确标题开头的数据或块包含多个标题。
如果您正在索引巨大的键值（比如有人试图索引一列 char(8192) 或 blob(8192)），则键可能不适合单个块，需要并排跨两个块溢出. 这意味着您的第一个块将有一个偏移标头，而第二个块将立即以关键数据开始。
所有这些的解决方案是拥有一个不可调整的固定数据库块大小并围绕它开发标题块数据结构......例如，您将所有块大小固定为 4KB（通常是最佳的）并编写一个非常小的以“区块类型”开头的区块头。如果它是一个普通块，那么紧跟在块头之后的应该是偏移头。如果是“溢出”类型，则紧跟在块头之后的是原始密钥数据。
更新（潜在的很棒的上行）
在块作为一系列字节读入并解码偏移量之后；从技术上讲，您可以简单地将您正在搜索的密钥编码为原始字节，然后对字节流进行直接比较。
一旦找到您要查找的密钥，就可以对指针进行解码和跟踪。
格雷格想法的另一个令人敬畏的副作用！这里 CPU 时间优化的潜力足够大，为了获得所有这些，设置一个固定的块大小可能是值得的。
您可以将索引作为固定大小的偏移量列表存储到包含关键数据的块中。例如：
+--------------+
| 3 | number of entries
+--------------+
| 16 | offset of first key data
+--------------+
| 24 | offset of second key data
+--------------+
| 39 | offset of third key data
+--------------+
| key one |
+----------------+
| key number two |
+-----------------------+
| this is the third key |
+-----------------------+
（好吧，关键数据将在一个真实的例子中排序，但你明白了）。
请注意，这不一定反映索引块在任何数据库中的实际构造方式。这仅仅是你如何一个例子可以组织索引数据的块，其中关键数据的长度是可变的。