上一篇文章（參見文末鏈接）介紹了數據庫系統體系架構，基於內存與磁盤存儲的數據庫管理系統的差異，以及行式存儲和列式存儲數據系統。這篇文章就要介紹數據庫系統的數據文件和索引文件。
數據文件和索引文件
數據庫系統的主要目的是存儲數據和快速檢索數據。但是數據該如何存儲才能實現快速檢索呢？是使用文件來存儲數據嗎？答案是數據庫系統確實使用文件來存儲數據，但是數據會以特殊的格式來保存到文件中。特殊的存儲格式可以確保：
- 存儲效率最高：存儲每條數據記錄的額外開銷最小。
- 訪問效率最高：數據記錄能夠以最少的步驟被訪問。
- 更新效率最高：對磁盤數據做最少改動就能完成記錄更新。
數據庫系統的表中存儲了由多個字段構成的數據記錄，每個表保存在一個單獨的文件中。表中的每一條記錄可以通過搜索鍵查找到，為了能快速從文件中查找到對應記錄，數據庫系統使用索引。索引實際上是一種特殊的數據結構，它可以幫助在數據文件中快速定位數據記錄，而且不需要掃描整個數據文件中的所有數據記錄。通常索引會在一個或一組能夠能識別數據記錄的字段上構建。
通常數據庫系統的數據記錄和索引是分別存儲到不同文件中的：數據文件存儲數據記錄；而索引文件索引數據。索引文件通常比數據文件小，通過索引文件中的數據就可以快速定位數據文件中記錄位置。
數據文件
數據文件(有時也稱為主文件)通常有三種組織形式： 堆組織表(heap-organized tables, heap files)、索引組織表(index-organized tables) 或 散列組織表(hash-organized tables, hashed files)。
- 堆組織表(heap-organized tables)，記錄不需要遵循任何特定的順序，大多數情況下它們在文件中按寫入順序排列，當添加新記錄時不需要進行任何文件內容的調整。但它需要額外的索引結構指向存儲的數據記錄的位置，以便進行搜索。
- 索引組織表(Index-Organized Table) 將索引和數據記錄存儲在一起。以主鍵進行排序，二叉樹的形式對錶的數據進行存儲。因為索引組織表已經按照主鍵對數據進行了排序，查找某個範圍記錄的效率非常的高。
- 散列組織表（hash-organized tables）中存儲單位是桶（bucket），每個桶中包含若干條記錄。主鍵的散列值決定了一條記錄應該存儲的桶。每個桶中的記錄可以按添加順序，也可以按主鍵排序存儲。
如果是數據和索引存儲在同一個文件中，搜索時可以減少至少一次磁盤尋道，因為遍歷索引找到鍵後既找到了數據記錄，不需要再從獨立的數據文件中讀取數據記錄。
當數據存儲在單獨的文件中時，索引文件保存的條目（data entries）可以唯一地標識數據記錄，幷包含足夠的信息來在數據文件中定位該記錄。例如，可能包含了數據文件中該記錄的偏移量，或者散列文件中的桶ID。如果是索引組織的表，條目保存就是實際的數據記錄。
索引文件
索引是一種能幫助高效磁盤數據檢索的數據結構。通常索引具有特殊的數據結構，該結構能映射鍵到鍵對應數據記錄在數據文件中的位置。
主文件(數據文件)上的索引稱為主索引。在大多數情況下，主索引構建在主鍵上，主鍵可以是一個鍵也可以是一組能標識記錄的鍵。所有其他索引都稱為輔助索引（Secondary indexes）。
輔助索引可以直接映射到數據記錄位置，或者只是簡單的映射到記錄所對應的主鍵。多個輔助索引可以指向相同的記錄，從而允許通過不同的字段和不同的索引來查找單個數據記錄。主索引文件為每個搜索鍵保存唯一一個條目，而次索引可能為每個搜索鍵保存多個條目。
如果數據記錄的順序和搜索鍵的順序一致，則此索引稱為聚簇索引。這種情況下索引和的數據記錄通常存儲在相同的文件中。如果數據存儲在單獨的文件中，並且其順序和鍵的順序不一致，則該索引稱非非聚簇索引。
在圖1-5中，a部分的輔助索引的一個搜索鍵指向了兩個數據記錄；b部分的輔助索引通過主鍵間接的指向數據記錄。
圖1-5
許多數據庫系統都有自帶顯式主鍵對應唯一一條數據庫記錄。在沒有指定主鍵的情況下，存儲引擎可以創建一個隱式主鍵(如，MySQL InnoDB會添加一個自動遞增列)。
上面這些術語和概念適用於不同類型的數據庫系統:關係數據庫系統(如MySQL和PostgreSQL)、基於dynamo的NoSQL數據庫(如Apache Cassandra和Riak)和文檔存儲數據庫(如MongoDB)。雖然在具體數據庫上命名可能會有一些不同，但多數情況下和上面這些術語一一對應。
以主索引為間接層
對於輔助索引是直接保存數據記錄位置信息，還是保存數據記錄的主鍵從而間接的指向數據記錄，數據庫社區大家看法不盡相同。事實上這兩種方法各有利弊，在具體應用場景下討論才具有意義。輔助索引直接保存數據記錄位置可以減少磁盤查找尋道時間，但是當數據記錄更新時或移動時必須要同時更新輔助索引中保存的數據記錄位置信息；通過主鍵的形式間接指向數據記錄雖然可以減少索引維護成本，但是由於磁盤讀取的原因讀取數據記錄的成本更高。
如果應用中大量的是讀操作較少的寫操作，更新所有索引保存的數據記錄位置信息可能不會有太大的問題。但是，如果應用中大部分都是寫操作，每次都要更新所有索引中的位置信息就可能帶來比較大的性能開銷了。為了減少更新索引中保存的數據記錄位置信息帶來的開銷，一些數據庫的實現中通過主鍵而引入一個間接層，即輔助索引通過指向主鍵而非直接保存數據記錄位置信息。 例如， MySQL InnoDB在執行查詢時，首先會在輔助索引上查找到主鍵，然後再通過主索引查詢數據記錄的位置。這種方式由於不是直接從輔助索引獲取到數據記錄的位置，因而會增加一次主索引查找的開銷。
圖1-6顯示了這兩種方法的不同之處: a) 主索引和輔助索引都直接保存了數據記錄的位置信息；b) 輔助索引保存數據記錄的主鍵，通過主索引間接的指向數據記錄的位置；
圖1-6
也有同時使用兩種兩種方式的，數據記錄的主鍵和位置信息都被保存在輔助索引中。如果數據位置信息已經失效的情況下，通過主索引定位數據記錄，最後更新輔助索引中失效的位置信息。
閱讀更多 壹瓜壹果 的文章
