讓我們從鍵值數(shù)據(jù)的索引開始璧瞬。這不是你可以索引的唯一類型的數(shù)據(jù)金蜀，但它非常常見毙死，而且它是構(gòu)建更復雜索引的一個有用的模塊柜去。
鍵值存儲與大多數(shù)編程語言中可以找到的dictionary類型非常相似，通常是作為散列表實現(xiàn)的郊酒。在許多算法教科書中都描述了哈希映射遇绞，因此我們不會詳細討論它們是如何工作的。既然我們已經(jīng)有了內(nèi)存數(shù)據(jù)結(jié)構(gòu)的哈希映射燎窘，為什么不使用它們來索引磁盤上的數(shù)據(jù)呢?
假設(shè)我們的數(shù)據(jù)存儲只包括追加記錄到一個文件摹闽，就像前面的例子一樣。然后褐健，最簡單的索引策略是:保存一個內(nèi)存中的散列映射付鹿，其中每個鍵都映射到數(shù)據(jù)文件中的一個字節(jié)偏移位置，這個位置的值如圖3-1所示可以被找到蚜迅。當你在文件中添加新的鍵值對時舵匾，您還將更新散列映射以反映您剛剛編寫的數(shù)據(jù)的偏移量（這既用于插入新鍵，也用于更新現(xiàn)有的鍵）谁不。當您想查找一個值時坐梯，使用散列映射來查找數(shù)據(jù)文件中的偏移量，查找該位置刹帕，并讀取該值吵血。
這聽起來可能過于簡單蹋辅，但卻是可行的方法钱贯。實際上，這就是Bitcask (Riak的默認存儲引擎）所做的事情晕翠。Bitcask提供高性能的讀寫喷舀，根據(jù)要求，所有的鍵都可以放在可用的RAM中淋肾，因為哈希映射被完全保存在內(nèi)存中硫麻。這些值可以使用比可用內(nèi)存更多的空間，因為它們可以從磁盤上加載樊卓。如果數(shù)據(jù)文件的那一部分已經(jīng)在文件系統(tǒng)緩存中拿愧，那么read不需要任何磁盤I/O。
像Bitcask這樣的存儲引擎非常適合于每個密鑰的值經(jīng)常更新的情況碌尔。例如浇辜，密鑰可能是一只貓的視頻URL，其值可能是它被播放的次數(shù)（每次有人點擊播放按鈕時遞增）唾戚。在這種模式中柳洋，有很多寫操作，但是沒有太多不同的鍵——每個鍵有大量的寫叹坦，但是將所有的鍵保存在內(nèi)存中是可行的熊镣。
到目前為止，我們只討論了追加記錄到文件中募书，那么如何避免最終耗盡磁盤空間呢?一個好的解決方案是绪囱，當它達到一定的大小時，關(guān)閉一個segment文件莹捡，然后將其寫入一個新的segment文件鬼吵，從而將日志分割成一定大小的segment。然后我們可以對這些片段執(zhí)行壓縮篮赢，如圖3-2所示齿椅。壓縮意味著在日志中丟棄重復的鍵启泣，并且只保留每個鍵的最新更新媒咳。
此外种远，由于壓縮常常使segment更小（假設(shè)一個鍵在一個segment內(nèi)平均覆蓋了幾次）顽耳，我們還可以同時合并多個segment坠敷，同時執(zhí)行壓縮妙同，如圖3-3所示。segment在寫入后不會被修改膝迎，因此合并的segment被寫入到一個新文件中粥帚。歷史segment的合并和壓縮可以在后臺線程中完成，而在進行的過程中限次，我們?nèi)匀豢梢允褂门f的segment文件繼續(xù)服務讀和寫請求芒涡。在合并過程完成之后，我們將讀取請求改為使用新的合并segment而不是舊的segment卖漫，然后刪除舊的segment文件费尽。
每個segment現(xiàn)在都有自己的內(nèi)存哈希表，映射鍵來進行文件偏移羊始。為了找到密鑰的值旱幼，我們首先檢查最近segment的散列映射；如果密鑰不存在突委，我們將檢查第二個最近的部分柏卤。。匀油。合并進程保持了segment的數(shù)量很少缘缚，所以查找不需要檢查很多散列映射。
這個簡單的想法在實踐中有很多細節(jié)敌蚜。簡而言之桥滨，真正實施的一些重要問題是:
文件格式
CSV不是日志的最佳格式。使用二進制格式（以字節(jié)為單位編碼字符串的長度）和原始字符串（不需要轉(zhuǎn)義)會更快更簡單钝侠。
刪除記錄
如果您想刪除一個鍵及其相關(guān)值该园，則必須將一個特殊的刪除記錄附加到數(shù)據(jù)文件（有時稱為tombstone）。當segment被合并時帅韧，tombstone告訴合并進程放棄刪除鍵的任何先前值里初。
崩潰恢復
如果數(shù)據(jù)庫重新啟動，內(nèi)存中的散列映射就會丟失忽舟。原則上双妨，你可以通過從頭到尾讀取整個segment文件來恢復每個segment的哈希映射，并注意在進行過程中每個鍵的最新值的偏移量叮阅。但是刁品，如果segment文件很大，這可能需要很長時間浩姥，這會使服務重啟很痛苦挑随。Bitcask通過在磁盤上存儲每個segment的散列映射的快照來加速恢復，這可以更快地加載到內(nèi)存中勒叠。
部分文字記錄
數(shù)據(jù)庫可能在任何時候崩潰兜挨，包括將記錄追加到日志的過程中膏孟。Bitcask文件包括校驗和，允許檢測和忽略該日志中損壞的部分拌汇。
并發(fā)控制
由于寫入是嚴格按順序添加到日志中的柒桑，所以一個常見的實現(xiàn)選擇是只有一個寫線程。數(shù)據(jù)文件segment是只允許追加噪舀，而且是不可變的魁淳，以便于可以通過多個線程并發(fā)地讀取它們。
一個只允許追加的文件第一眼看上去很浪費：為什么不更新文件与倡，用新值重寫舊值界逛？但是只允許追加的設(shè)計是好的，有幾個原因：
- 追加和segment合并是順序?qū)懖僮髡糇撸ǔ１入S機寫快得多仇奶，特別是在magnetic spinning-disk硬盤上。在某種程度上比驻，順序?qū)懺诨陂W存的固態(tài)硬盤（ssd）上也更可取该溯。我們將在后面的“比較BTrees和LSM-Trees”中進一步討論這個問題。
- 如果segment文件是只允許追加的或不可變的别惦，那么并發(fā)和崩潰恢復要簡單得多狈茉。例如，您不必擔心發(fā)生崩潰時當一個值被覆蓋掸掸，會留下一個包含舊值的一部分氯庆，同時又將新值的一部分拼接在一起的文件。
- 合并舊的segment可以避免數(shù)據(jù)文件隨著時間的推移而變得支離破碎的問題扰付。
然而堤撵，哈希表索引也有限制：
- 哈希表必須適合內(nèi)存，所以如果你有非常多的鍵羽莺，你就不走運了实昨。原則上，您可以在磁盤上維護一個散列映射盐固，但不幸的是荒给，很難使磁盤上的哈希映射執(zhí)行良好。它需要大量的隨機訪問I/O刁卜，而且當它很大時志电，再增長的代價就比較昂貴了，并且散列沖突也需要復雜的邏輯蛔趴。
- 范圍查詢無效挑辆。例如，您不能輕松地掃描kitty00000和kitty99999之間的所有key，您必須在散列映射中單獨查找每個鍵之拨。
在下一節(jié)中茉继，我們將研究一個沒有這些限制的索引結(jié)構(gòu)。
