一、NTFS文件系統的B+樹結構與一般的B+樹結構的區別
NTFS文件系統的B+樹結構與一般的B+樹結構的區別是NTFS文件系統的B+樹結構是配合磁盤特性的,本來查詢樹使用多分支在內存里是沒有意義的,只會導致讀取了更多數據。但磁盤(或者說機械硬盤)的特性在于,多次隨機讀取效率遠低于連續讀取一大段數據,因為每一次都需要經過尋道。這樣B樹就被設計為用較少的次數讀取磁盤,每次讀取較大的塊,從而優化整體查詢。
B+樹在NTFS文件系統中的應用
卷(volume)
NTFS的結構首先從卷開始。
卷相應于磁盤上的一個邏輯分區,當你將一個磁盤或者磁盤的一部分格式化成NTFS,卷將被創建起來。
一個磁盤能夠有一個卷或好幾個卷.NTFS獨立的處理每個卷。
卷相應的就是C盤,D盤,E盤等。
簇(cluster)
在一個NTFS卷中,簇的大小,或者說簇因子(cluster factor),是在磁盤管理程序MMC載入件格式化該卷的時候建立起來的。默認的簇因子隨著卷大小的不同而不同,但它是物理扇區的整數倍。并且總是2的冪。(1個扇區,2個扇區,4個扇區,8個扇區)以此類推。
簇因子被表示成一個簇中的字節數,比方512字節 1KB或者2KB。
硬盤的讀寫以扇區為基本單位。NTFS的讀寫以簇為基本單位。
NTFS在內部僅僅引用到簇一級,NTFS使用簇作為它的分配單位,從而保持它與物理扇區大小之間的獨立性。
邏輯簇號(Logical Cluster Number。LCN)
LCN是從一個卷的開始直到結束的全部簇的一個編號。
NTFS依賴于邏輯號(LCN)來引用物理位置。
獲取物理磁盤地址方法
LCN乘以簇因子。從而得到卷上的物理字節偏移量。
虛擬簇號(Virtual Cluster Number。VCN)
VCN對同屬一個文件的全部簇進行編號,從0到m。NTFS依賴于虛擬簇號(VCN)來引用一個文件內部的數據。
VCN不必是物理上連續的。它們能夠被映射到該卷上的不論什么LCN編號。
主文件表(Master File Table)
MFT是NTFS卷結構的核心所在。
涉及到B+樹。
延伸閱讀:
二、什么是B樹
B樹是一種數據結構,用于在硬盤或其他非易失性存儲介質上快速存儲和訪問大量數據。它是一種平衡樹,其每個節點可以存儲多個鍵值對,而不僅僅是一個。B樹通常用于需要頻繁讀寫的數據庫或文件系統中,因為它可以減少磁盤的訪問次數,從而提高了性能。
B樹有以下幾個特點:
每個節點可以存儲多個鍵值對。這個數量通常稱為節點的度數(degree)。
所有葉節點都在同一層級上。這有助于保持樹的平衡,使得在任何一個節點到達葉子節點的路徑長度都相同。
節點中的鍵值對是按照某種順序排列的。這使得查找操作更加高效。
B樹的高度相對于存儲的關鍵字數來說非常小。因此,可以較快地定位到任何一個關鍵字。