Ch3: Storage and Retrieval
第三章: 存儲與檢索
常見資料架構 ( 格式 ) 有: Hash Indexes、SSTables、LSM tree、B tree …
Hash Indexes :
當輸入值經由 hash function 運算之後到達第一個 hashed index 的位置，便可以得到一筆 data page 的位置而取得資料，然後要往下一個 hashed index 移動，如果 hashed value 也是一樣的話，就要再取得它對應的 data page 之資料，直到 hashed index 的值不同或是沒有下一個。
相對的當串列中有其中一點 hashed index 遺失，將導致後續資料都連帶遺失，且要尋找一項資料需由源頭一路找，效能相對不佳。
SSTables （Sorted String Table）:
SSTable 是 Bigtable 內部用於數據的文件格式，它的格式為文件本身就是一個排序的、不可變的、持久的 key / value，其中 key 和 value 都可以是任意的 byte 字符串。使用 key 來查找 value。每個 SSTable 包含一系列的 block，在 SSTable 的末尾是 block 索引，這些索引在 SSTable 打開時被加載到內存中，在查找時首先從內存中的索引二分查找找到 block，然後一次磁盤尋道即可讀取到相應的 block。
SSTables 有以下幾項優點:
1. 合併是簡單且高效的，即使文件大於可用內存。這種方法就像合併排序 (Merge sort) 使用的方法一樣，首先並排輸入文件，再查看每個文件中的第一個 key，複製最低 key（根據順序排序）到輸出文件且重複。這產生一個新的合併文件且依照 key 排序。
2. 可由已知的 A 與 B 的偏移，進而由 A 的偏移位置並從那裡掃描，尋找於 A 與 B 之間的目標 key（若該文件中沒有該鍵則找不到），進而加速尋找速度。
3. 當讀取請求時，皆需要掃描所有請求內的 key - value，因此可以分組記錄，再將其寫入磁盤之前對其進行壓縮 。稀疏內存中的索引，每個條目都指向壓縮塊的開始處，除了節省磁碟空間之外，壓縮還可以減少 IO 頻寬 (Bandwidth) 的使用。
LSM Tree (Log Structured Merge Tree):
上面提到的這個機制已經實做在 LevelDB 和 RocksDB 中，類似的儲存引擎 (storage engine) 也使用在 Cassandra 和 HBase 裡，這 2 個都是啟發自 Google 的 BigTable 論文，起初，這個 indexing 結構是 Patrick O’Neil 提出的 論文 ，將此結構稱為 Log Structured Merge Tree (或 LSM Tree)。
B tree (Balance Tree):
是一種自平衡的樹，能夠保持數據有序。這種資料結構能夠讓查找數據、順序訪問、插入數據及刪除的動作，都在對數時間內完成。
概括來說是一個一般化的二元搜尋樹（binary search tree）一個節點可以擁有2個以上的子節點，與自平衡二元搜尋樹不同，B 樹適用於讀寫相對大的數據塊的存儲，例如磁碟。B 樹減少定位記錄時所經歷的中間過程，從而加快存取速度。B 樹這種資料結構可以用來描述外部存儲。這種資料結構常被應用在資料庫和文件系統的實現上。
B+ Tree
B Tree 有許多種，其中最常見的是 B+ Tree， MySQL 就普遍使用B+Tree 實現其索引結構。
B+ Tree 插入與修改擁有較穩定的對數時間複雜度，且資料有序。B+ Tree 資料由下而上插入，通過最大化內部節點內的子節點的數目減少樹的高度，且樹平衡操作不常發生，進而增加效率。通常每個節點在次級儲存中占據完整的磁碟塊或近似的大小。
SQL 以 B+Tree 存儲基於鍵的持久化索引。 樹中的每個節點都由一個頁面表示。 數據頁面構建樹的葉級，而所有其他節點由單個頁面組成，如下圖:
OLTP 系統為了處理負載，應用程式通常只訪問每個查詢中的少部分記錄。應用程式使用某種鍵來請求記錄，存儲引擎使用索引來查找所請求的鍵的資料。磁碟找尋的時間往往是瓶頸。
資料倉庫和類似的分析系統會低調一些，因為它們主要由業務分析人員使用，而不是由最終用戶使用。它們的查詢量要比 OLTP 系統少得多，但通常每個查詢開銷高昂，需要在短時間內掃描數百萬條記錄。磁片頻寬（而不是查找時間）往往是瓶頸，列式存儲是這種工作負載越來越流行的解決方案。
