磁盤數據結構的體系結構

Question

最近我終於理解磁盤btrees的體系結構是this。

這很簡單，很容易閱讀和理解。但我仍然感到困惑。它似乎沒有任何內存數據結構。我錯過了什麼嗎？是什麼使這是一個btree？它是否只是「指向」其子節點的鍵的長整型數組？這是否有效？這就是大多數數據庫和文件系統的設計方式嗎？

有沒有在內存中實現磁盤btrees（或其他數據結構）的方法？每個節點包含文件偏移量還是其他？

Answer 1

節點指針通常作爲地址存儲在磁盤上（例如使用長整數）。

一般的實現選擇使用物理或邏輯地址：

• 物理地址指定的實際偏移量（在文件內或類似的），其中該節點被存儲。
• 相比之下，邏輯地址需要某種機制，每次指針被導航/遍歷時都會解析爲物理地址。

物理尋址速度更快（因爲不需要解析機制）。但是，邏輯尋址可以允許節點重新組織而不必重寫指針。能夠以這種方式重新組織節點的能力可以用作實現良好集羣，空間利用率甚至低級別數據分配的基礎。

一些實現使用邏輯和物理尋址的組合，使得每個地址由（動態地）引用段（blob）和該段內的物理地址的邏輯地址組成。

重要的是要注意節點地址是基於磁盤的，因此它們不能直接轉換到內存中指針。

在某些情況下，將數據加載到內存中（然後在寫入時轉換回基於磁盤的指針）將基於磁盤的指針轉換爲內存指針是有益的。

該轉換有時被稱爲指針調配，並且可以用很多方式實現。其基本思想是調用的數據在指針被導航/遍歷之前不應該被加載到內存中，內存指針。

常見的方法是使用邏輯內存尋址方案或使用內存映射文件。內存映射文件使用虛擬內存尋址，其中內存頁面在訪問之前不會加載到內存中。虛擬內存映射文件由操作系統提供。這種方法有時被稱爲頁錯誤尋址，因爲訪問未映射到內存的內存頁上的數據還會導致頁錯誤中斷。