本篇文章給大家分享的是有關(guān)如何利用leveldb實(shí)現(xiàn)文件系統(tǒng)的目錄樹，小編覺得挺實(shí)用的，因此分享給大家學(xué)習(xí)，希望大家閱讀完這篇文章后可以有所收獲，話不多說，跟著小編一起來看看吧。

創(chuàng)新互聯(lián)建站專注于企業(yè)網(wǎng)絡(luò)營(yíng)銷推廣、網(wǎng)站重做改版、東安網(wǎng)站定制設(shè)計(jì)、自適應(yīng)品牌網(wǎng)站建設(shè)、H5響應(yīng)式網(wǎng)站、成都商城網(wǎng)站開發(fā)、集團(tuán)公司官網(wǎng)建設(shè)、外貿(mào)網(wǎng)站建設(shè)、高端網(wǎng)站制作、響應(yīng)式網(wǎng)頁設(shè)計(jì)等建站業(yè)務(wù)，價(jià)格優(yōu)惠性價(jià)比高，為東安等各大城市提供網(wǎng)站開發(fā)制作服務(wù)。

利用leveldb實(shí)現(xiàn)文件系統(tǒng)的目錄樹

目錄樹維護(hù)了整個(gè)文件系統(tǒng)的元信息，所有對(duì)文件系統(tǒng)中文件的增刪查改操作都首先需要經(jīng)過目錄樹的操作才能進(jìn)行。百度開源的分布式文件系統(tǒng)BFS(開源地址：https://github.com/baidu/bfs)利用leveldb，實(shí)現(xiàn)了目錄樹的管理，使得目錄樹的實(shí)現(xiàn)非常簡(jiǎn)潔，同時(shí)對(duì)目錄樹的操作十分高效。本文將為你解析其具體設(shè)計(jì)及實(shí)現(xiàn)思路。

目錄樹為一個(gè)樹型結(jié)構(gòu)，而leveldb是一個(gè)kv存儲(chǔ)引擎，因此，如果想用通過leveldb實(shí)現(xiàn)目錄樹，則需要把樹型結(jié)構(gòu)映射成kv的扁平化結(jié)構(gòu)。

單獨(dú)就每個(gè)文件或者目錄來講，其信息只需要一條kv記錄即可保存，而這條kv中的value需要保存該目錄或文件的屬性信息，可變動(dòng)的空間不大。所以，從樹型結(jié)構(gòu)到kv記錄的映射 ，關(guān)鍵在于key的選取。

在BFS的目錄樹中，定義了一個(gè)int64_t的整型數(shù)字作為EntryID，每個(gè)文件或目錄擁有一個(gè)EntryID，并且全局唯一，根目錄的EntryID規(guī)定為1。假設(shè)有如下目錄結(jié)構(gòu)：

/home/dirx/
          /filex
      diry/
          /filey
/tmp/
     filez

按照創(chuàng)建順序，我們依次給/home分配的EntryID為2，/tmp的EntryID為3，/home/dirx的EntryId為4，/home/diry的EntryID為5，/home/tmp/filez的EntryID為6，/home/dirx/filex的EntryID為7，/home/diry/filey的EntryID為8。

注意到每個(gè)目錄擁有一個(gè)自己的EntryID的同時(shí)，又肯定擁有一個(gè)父目錄，其父目錄又肯定擁有一個(gè)EntryID，可以利用這一點(diǎn)，通過父目錄的EntryID和子目錄中的文件名，來確定一條記錄的key：對(duì)于每個(gè)文件或者目錄，我們規(guī)定：每條kv記錄的key為 "父目錄的EntryID+自身文件名"，同時(shí)在value中存儲(chǔ)自己的EntryID這樣編碼后，上述目錄樹便可以表示為如下kv記錄：

1home -> 2 + xxx
1tmp -> 3 + xxx
2dirx -> 4 + xxx
2diry -> 5 + xxx
3filez -> 6 + xxx
4filex -> 7 + xxx
5filey -> 8 + xxx

其中，xxx表示該目錄或文件的其它信息，如大小，創(chuàng)建時(shí)間，實(shí)際數(shù)據(jù)存放位置等。

到此，目錄樹這個(gè)樹型結(jié)構(gòu)，便已經(jīng)平展成為一條條的kv記錄，對(duì)目錄樹的操作，便轉(zhuǎn)化成了對(duì)某幾條kv記錄的操作：

• 對(duì)于創(chuàng)建文件操作，比如想創(chuàng)建/home/work/目錄，則首先在/目錄中查找home目錄，由于/的EntryID為1，所以第一次查找時(shí)，key為1home，然后讀出其value，解析后發(fā)現(xiàn)/home的EntryID為2，則將此EntryID記下，繼續(xù)往下走，發(fā)現(xiàn)work即為所需要?jiǎng)?chuàng)建的文件，則為其申請(qǐng)一個(gè)EntryID（假設(shè)為9），此時(shí)，寫入一條記錄，按照上面的規(guī)則，其key為2work，value為work創(chuàng)建的時(shí)間等信息，以及work的EntryID（9）

• 對(duì)于刪除操作，比如把剛剛創(chuàng)建的/home/work目錄刪除，只需要將key為2work的這條記錄刪除即可

• 對(duì)于讀取操作，比如想讀取/home/dirx/filex文件中的內(nèi)容，則首先讀取1home這條key所對(duì)應(yīng)的value，解析發(fā)現(xiàn)value中記錄的EntryID為2，然后再去讀取2dirx這條key所對(duì)應(yīng)的value，解析發(fā)現(xiàn)value中記錄的EntryID為4，然后再去讀取4filex這條key所對(duì)應(yīng)的value，從里面解析出/home/dirx/filex的實(shí)際數(shù)據(jù)存放位置，進(jìn)行文件內(nèi)容的讀取

• 對(duì)于List目錄操作，比如想看看根目錄下有哪些文件和目錄，由于每個(gè)文件和目錄在存儲(chǔ)時(shí)，其key中都包含父目錄的EntryID，因此，只需進(jìn)行一次掃描即可。比如ls /，則只需掃描leveldb中，以1\0x0為前綴的key即可，當(dāng)遇到2時(shí)停止，所得結(jié)果即為/目錄下的所有內(nèi)容

• 對(duì)于Rename操作，只需要改動(dòng)其key即可。比如想要把/home/diry/filey文件移動(dòng)到home/dirx目錄中，按照之前的規(guī)則，/home/diry/filey在leveldb中存儲(chǔ)的key為5filey，/home/dirx的EntryID為4，把5filey這條記錄中的內(nèi)存讀取出來，以4filey為key，再次存儲(chǔ)到leveldbk ，然后將5filey這條記錄刪除，即完成了Rename操作

這樣，一個(gè)目錄樹所需要的基本操作便已經(jīng)支持，由于leveldb引擎本身寫入速度較快，并且在讀取時(shí)，內(nèi)部本身已經(jīng)有cache來緩存住較熱的kv數(shù)據(jù)，并且緩存大小可配置，所以一個(gè)非常簡(jiǎn)潔高效的目錄樹便實(shí)現(xiàn)了~

以上就是如何利用leveldb實(shí)現(xiàn)文件系統(tǒng)的目錄樹，小編相信有部分知識(shí)點(diǎn)可能是我們?nèi)粘９ぷ鲿?huì)見到或用到的。希望你能通過這篇文章學(xué)到更多知識(shí)。更多詳情敬請(qǐng)關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道。