數據庫如何為可變長度欄位儲存索引鍵值（在磁碟上）？
語境
這個問題與 SQL 和 NoSQL 數據庫系統中索引的低級實現細節有關。索引的實際結構（B+ 樹、雜湊、SSTable 等）是無關緊要的，因為該問題專門與儲存在任何這些實現的單個節點內的鍵有關。
背景
在 SQL（例如 MySQL）和 NoSQL（CouchDB、MongoDB 等）數據庫中，當您在數據的列或 JSON 文件欄位上建構索引時，您實際上導致數據庫執行的操作本質上是創建所有排序的列表這些值以及與該值有關的記錄所在的主數據文件中的文件偏移量。
（為簡單起見，我可能會放棄特定 impl 的其他深奧細節）
簡單的經典 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”，經典的數據庫索引查找如下：
- 讀取索引的根（在本例中為 1 個塊）
- 對已排序的塊進行二進制搜尋以找到鍵
- 從值中獲取數據文件偏移量
- 使用偏移量查找數據文件中的記錄
- 將數據返回給呼叫者
問題設置…
好的，這就是問題所在……
第 2 步是最重要的部分，它允許這些查詢在 O(logn) 時間內執行…資訊必須進行排序，但您必須能夠以快速排序的方式遍歷列表…更多具體來說，您必須能夠隨意跳轉到明確定義的偏移量才能讀取該位置的索引鍵值。
讀完block後，你要能馬上跳到第170個位置，讀key值，看看你要找的是GT還是LT那個位置（以此類推……）
您能夠像這樣在塊中跳轉數據的唯一方法是，如果鍵值大小都是明確定義的，就像我們上面的範例一樣（每個鍵 4 字節，然後 8 字節）。
題
好的，這就是我陷入高效索引設計的地方……對於 SQL 數據庫中的 varchar 列，或者更具體地說，是 CouchDB 或 NoSQL 等文件數據庫中完全自由格式的欄位，您想要索引的任何欄位都可以是任何長度如何實現建構索引的索引結構塊內的鍵值？
例如，假設您在 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 個或更少的偏移量，導致需要讀入的數字塊非常小。
更新（Greg 建議的潛在缺點）
為了最好地繼續與我自己進行此對話，我意識到了以下缺點…
- 如果每個“塊”都以偏移數據開頭，那麼您以後就不能允許在配置中調整塊大小，因為您最終可能會讀取沒有正確以標題開頭的數據或塊包含多個標題。
- 如果您正在索引巨大的鍵值（例如有人試圖索引 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 | +-----------------------+（嗯，關鍵數據將在一個真實的例子中排序，但你明白了）。
請注意，這不一定反映索引塊在任何數據庫中的實際構造方式。這只是一個範例，說明如何組織索引數據塊，其中鍵數據是可變長度的。