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 系統少得多,但通常每個查詢開銷高昂,需要在短時間內掃描數百萬條記錄。磁片頻寬(而不是查找時間)往往是瓶頸,列式存儲是這種工作負載越來越流行的解決方案。