數據庫索引介紹

索引

哈希索引

保留一個內存中的哈希映射，其中每個鍵都映射到一個數據文件中的字節偏移量，查找一個值時，使用哈希映射來查找數據文件中的偏移量，尋找（seek） 該位置并讀取該值。

局限性：散列表必須能放進內存；范圍查詢效率不高

SSTables

排序字符串表（Sorted String Table），要求鍵值對的序列按鍵排序，查詢時不再需要將所有的鍵保存在索引，只需存很稀疏的鍵就夠了。寫入操作：在磁盤上維護有序結構沒有內存簡單，內存中有很多樹形數據結構，例如紅黑樹或AVL樹。寫入時將數據寫入內存的樹結構中，當內存表大于某個閾值時，將其作為SSTable文件寫入磁盤。查詢操作：先嘗試在內存表中找到關鍵字，然后在最近的磁盤段中，然后在下一個較舊的段中找到該關鍵字。

問題：數據庫崩潰時，寫入內存的數據會丟失，可以通過記錄寫日志的方式解決（日志在內存表持久化后丟棄）。

B樹

B樹同樣保持按鍵排序的鍵值對，B樹將數據庫分解成固定大小的塊或頁面，傳統上大小為4KB（有時會更大），并且一次只能讀取或寫入一個頁面。每個頁面都可以使用地址或位置來標識，一個頁面引用另一個頁面地址。

寫入操作：如果要更新B樹中現有鍵的值，則搜索包含該鍵的葉頁，更改該頁中的值，并將該頁寫回到磁盤（對該頁的任何引用保持有效） 。如果你想添加一個新的鍵，你需要找到其范圍包含新鍵的頁面，并將其添加到該頁面。如果頁面中沒有足夠的可用空間容納新鍵，則將其分成兩個半滿頁面，并更新父頁面以解釋鍵范圍的新分區。

聚集索引

從索引到堆文件的額外跳躍對讀取來說性能損失太大，因此可能希望將索引行直接存儲在索引中。在MySQL的InnoDB存儲引擎中，表的主鍵總是一個聚集索引，二級索引則引用主鍵，Myisam引擎中是非聚集索引，數據存儲在堆文件中而非葉子結點。

在內存中存儲一切

隨著RAM變得更便宜，將數據全部保存在內存中是非常可行的。通過消除與管理磁盤上的數據結構相關的所有開銷，內存數據庫可以提供巨大的性能改進，如VoltDB，MemSQL。反直覺的是，內存數據庫的性能優勢并不是因為它們不需要從磁盤讀取的事實。即使是基于磁盤的存儲引擎也可能永遠不需要從磁盤讀取，因為操作系統在內存中緩存了最近使用的磁盤塊。相反，它們更快的原因在于省去了將內存數據結構編碼為磁盤數據結構的開銷。除了性能，內存數據庫的另一個有趣的領域是提供難以用基于磁盤的索引實現的數據模型。例如，Redis為各種數據結構（如優先級隊列和集合）提供了類似數據庫的接口。