iT邦幫忙

DAY 29
4

檔案系統的設計與效能系列 第 29

檔案系統的設計與效能 - B+ Tree

為了搜尋的效率,檔案系統一般會採用B+ TreeHash的方式來設計。今天我們先來談談B+ Tree的演算法。
之前我們談i-node時不斷的提到B+ Tree,因為檔案系統為了增進搜尋的效率所採用的資料結構。B+ Tree是一種平衡樹狀結構,資料記載於樹葉上,而由樹根到每個樹葉的長度是相同的。B+ Tree上所儲存的資料會經過排序過,並且透過指標一個個串起來,且看以下B+ Tree的搜尋演算法:

  function search(record r)
    u := root
    while (u is not a leaf) do
      choose the correct pointer in the node
      move to the first node following the pointer
      u := current node
    scan u for r

B+ Tree在進行搜尋的動作時,先找到索引(key)之後,就可以沿著指標找到/或沒找到資料。優點是速度快,但是缺點是占用較多的空間, 所以適合使用在磁碟(檔案系統)甚於記憶體中的應用。


上一篇
檔案系統的設計與效能 - Attributes
下一篇
檔案系統的設計與效能 - Hash
系列文
檔案系統的設計與效能32

1 則留言

0
食夢黑貘
iT邦研究生 4 級 ‧ 2010-11-01 22:54:33

事實上可以做一些演算法的比較會更好...

我要留言

立即登入留言