[TOC] ## 最簡單的kv庫 ``` #!/bin/bash db_set () { echo "$1,$2" >> database } db_get () { grep "^$1," database | sed -e "s/^$1,//" | tail -n 1 } ``` ``` $ db_set 123456 '{"name":"London","attractions":["Big Ben","London Eye"]}' $ $ db_set 42 '{"name":"San Francisco","attractions":["Golden Gate Bridge"]}' $ db_get 42 {"name":"San Francisco","attractions":["Golden Gate Bridge"]} ``` 因為沒有索引,所以查詢復雜度為 O(n), ## 哈希索引 最簡單的索引策略就是：保留一個內存中的哈希映射，其中每個鍵都映射到一個數據文件中的字節偏移量，指明了可以找到對應值的位置 當你將新的鍵值對追加寫入文件中時，還要更新散列映射，以反映剛剛寫入的數據的偏移量（這同時適用于插入新鍵與更新現有鍵） ***文件格式*** ? CSV不是日志的最佳格式。使用二進制格式更快，更簡單，首先以字節為單位對字符串的長度進行編碼，然后使用原始字符串（不需要轉義）。 ***刪除記錄*** 如果要刪除一個鍵及其關聯的值，則必須在數據文件（有時稱為邏輯刪除）中附加一個特殊的刪除記錄。當日志段被合并時，邏輯刪除告訴合并過程放棄刪除鍵的任何以前的值。 ***崩潰恢復*** 如果數據庫重新啟動，則內存散列映射將丟失。原則上，您可以通過從頭到尾讀取整個段文件并在每次按鍵時注意每個鍵的最近值的偏移量來恢復每個段的哈希映射。但是，如果段文件很大，這可能需要很長時間，這將使服務器重新啟動痛苦。 Bitcask通過存儲加速恢復磁盤上每個段的哈希映射的快照，可以更快地加載到內存中。 ***部分寫入記錄*** 數據庫可能隨時崩潰，包括將記錄附加到日志中途。 Bitcask文件包含校驗和，允許檢測和忽略日志的這些損壞部分 ***并發控制*** 由于寫操作是以嚴格順序的順序附加到日志中的，所以常見的實現選擇是只有一個寫入器線程。數據文件段是附加的，或者是不可變的，所以它們可以被多個線程同時讀取 使用追加日志而不是寫入文件是因為 - 追加和分段合并是順序寫入操作，通常比隨機寫入快得多，尤其是在磁盤旋轉硬盤上。在某種程度上，順序寫入在基于閃存的 固態硬盤（SSD） 上也是優選的 - 如果段文件是附加的或不可變的，并發和崩潰恢復就簡單多了。例如，您不必擔心在覆蓋值時發生崩潰的情況，而將包含舊值和新值的一部分的文件保留在一起。 - 合并舊段可以避免數據文件隨著時間的推移而分散的問題。 哈希表索引也有局限性: * 散列表必須能放進內存 * 范圍查詢效率不高。例如，您無法輕松掃描kitty00000和kitty99999之間的所有鍵——您必須在散列映射中單獨查找每個鍵。 ## SSTables和LSM樹 LSM 樹使用**排序字符串表**（Sorted Strings Table 簡稱 SSTable）的格式保存到磁盤。如名稱所示，SSTables 是一種用于存儲鍵-值對的格式，其中鍵按有序排列。SSTable 將由多個名為段（*Segments*）的有序文件組成。一旦將這些數據段寫入磁盤后，就是不可變的。簡化示例如下  ### 性能優化 當查找數據庫中不存在的鍵時，LSM樹算法可能會很慢：您必須檢查內存表，然后將這些段一直回到最老的（可能必須從磁盤讀取每一個），然后才能確定鍵不存在。為了優化這種訪問，存儲引擎通常使用額外的Bloom過濾器 ## B樹 我們前面看到的日志結構索引將數據庫分解為可變大小的段，通常是幾兆字節或更大的大小，并且總是按順序編寫段。相比之下，B樹將數據庫分解成固定大小的塊或頁面，傳統上大小為4KB（有時會更大），并且一次只能讀取或寫入一個頁面。這種設計更接近于底層硬件，因為磁盤也被安排在固定大小的塊中  圖3-6 使用B樹索引查找一個鍵 如果要更新B樹中現有鍵的值，則搜索包含該鍵的葉頁，更改該頁中的值，并將該頁寫回到磁盤（對該頁的任何引用保持有效） 。如果你想添加一個新的鍵，你需要找到其范圍包含新鍵的頁面，并將其添加到該頁面。如果頁面中沒有足夠的可用空間容納新鍵，則將其分成兩個半滿頁面，并更新父頁面以解釋鍵范圍的新分區 如果因為插入導致頁面過度而拆分頁面，則需要編寫已拆分的兩個頁面，并覆蓋其父頁面以更新對兩個子頁面的引用。這是一個危險的操作，因為如果數據庫在僅有一些頁面被寫入后崩潰，那么最終將導致一個損壞的索引（例如，可能有一個孤兒頁面不是任何父項的子項） 為了使數據庫對崩潰具有韌性，B樹實現通常會帶有一個額外的磁盤數據結構：**預寫式日志**（WAL, write-ahead-log）（也稱為**重做日志**（redo log））。這是一個僅追加的文件，每個B樹修改都可以應用到樹本身的頁面上。當數據庫在崩潰后恢復時，這個日志被用來使B樹恢復到一致的狀態 ### 比較B樹和LSM樹 盡管B樹實現通常比LSM樹實現更成熟，但LSM樹由于其性能特點也非常有趣。根據經驗，通常LSM樹的寫入速度更快，而B樹的讀取速度更快 ## LSM樹 ### 優點 B樹索引必須至少兩次寫入每一段數據：一次寫入預先寫入日志，一次寫入樹頁面本身（也許再次分頁）。即使在該頁面中只有幾個字節發生了變化，也需要一次編寫整個頁面的開銷。有些存儲引擎甚至會覆蓋同一個頁面兩次，以免在電源故障的情況下導致頁面部分更新 由于反復壓縮和合并SSTables，日志結構索引也會重寫數據。這種影響 —— 在數據庫的生命周期中寫入數據庫導致對磁盤的多次寫入 —— 被稱為**寫放大（write amplification）** ### 缺點 日志結構存儲的缺點是壓縮過程有時會干擾正在進行的讀寫操作。盡管存儲引擎嘗試逐步執行壓縮而不影響并發訪問，但是磁盤資源有限，所以很容易發生請求需要等待而磁盤完成昂貴的壓縮操作。對吞吐量和平均響應時間的影響通常很小，但是在更高百分比的情況下 ## 全文搜索和模糊索引 全文搜索引擎通常允許搜索一個單詞以擴展為包括該單詞的同義詞，忽略單詞的語法變體，并且搜索在相同文檔中彼此靠近的單詞的出現，并且支持各種其他功能取決于文本的語言分析 ## 在內存中存儲一切 諸如VoltDB，MemSQL和Oracle TimesTen等產品是具有關系模型的內存數據庫 反直覺的是，內存數據庫的性能優勢并不是因為它們不需要從磁盤讀取的事實。即使是基于磁盤的存儲引擎也可能永遠不需要從磁盤讀取，因為操作系統緩存最近在內存中使用了磁盤塊。相反，它們更快的原因在于省去了將內存數據結構編碼為磁盤數據結構的開銷