是這樣的,剛上的一節(jié)數(shù)據(jù)結(jié)構(gòu)課,學(xué)習(xí)了B樹.里面提到了B樹主要用于文件索引.書上的結(jié)構(gòu)體定義如下
#define m 3
typedef struct BTNode{
KeyType key[m+1];
struct BTNode* parent;
stuct BTNoded *children[m+1];
Record* recptr[m+1];
}BTNOde , *BTree;
但是文件的索引key究竟用什么進(jìn)行索引?我想不明白百度查到了在linux系統(tǒng)下的做法.
還有一個疑問是recptr指針如何定位到文件,這個我仍未查到,先紀(jì)錄,如果有dalao告訴我更好
--使用inode做文件的索引進(jìn)行查詢.
以下內(nèi)容轉(zhuǎn)載自 阮一峰 - 理解inode
一、inode是什么？
理解inode类少，要從文件儲存說起瘾英。
文件儲存在硬盤上顿天，硬盤的最小存儲單位叫做"扇區(qū)"（Sector）犀忱。每個扇區(qū)儲存512字節(jié)（相當(dāng)于0.5KB）拣展。
操作系統(tǒng)讀取硬盤的時候坡垫，不會一個個扇區(qū)地讀取梭灿，這樣效率太低，而是一次性連續(xù)讀取多個扇區(qū)冰悠，即一次性讀取一個"塊"（block）堡妒。這種由多個扇區(qū)組成的"塊"，是文件存取的最小單位溉卓。"塊"的大小皮迟，最常見的是4KB，即連續(xù)八個 sector組成一個 block桑寨。
文件數(shù)據(jù)都儲存在"塊"中伏尼，那么很顯然，我們還必須找到一個地方儲存文件的元信息尉尾，比如文件的創(chuàng)建者爆阶、文件的創(chuàng)建日期、文件的大小等等。這種儲存文件元信息的區(qū)域就叫做inode扰她，中文譯名為"索引節(jié)點(diǎn)"兽掰。
每一個文件都有對應(yīng)的inode，里面包含了與該文件有關(guān)的一些信息徒役。
二孽尽、inode的內(nèi)容
inode包含文件的元信息，具體來說有以下內(nèi)容：
- 文件的字節(jié)數(shù)
* 文件擁有者的User ID
* 文件的Group ID
* 文件的讀忧勿、寫杉女、執(zhí)行權(quán)限
* 文件的時間戳，共有三個：ctime指inode上一次變動的時間鸳吸，mtime指文件內(nèi)容上一次變動的時間熏挎，atime指文件上一次打開的時間。
* 鏈接數(shù)晌砾，即有多少文件名指向這個inode
* 文件數(shù)據(jù)block的位置
可以用stat命令坎拐，查看某個文件的inode信息：
stat example.txt
總之，除了文件名以外的所有文件信息养匈，都存在inode之中哼勇。至于為什么沒有文件名，下文會有詳細(xì)解釋呕乎。
三积担、inode的大小
inode也會消耗硬盤空間，所以硬盤格式化的時候猬仁，操作系統(tǒng)自動將硬盤分成兩個區(qū)域帝璧。一個是數(shù)據(jù)區(qū)，存放文件數(shù)據(jù)湿刽；另一個是inode區(qū)（inode table）的烁，存放inode所包含的信息。
每個inode節(jié)點(diǎn)的大小叭爱，一般是128字節(jié)或256字節(jié)撮躁。inode節(jié)點(diǎn)的總數(shù)漱病，在格式化時就給定买雾，一般是每1KB或每2KB就設(shè)置一個inode。假定在一塊1GB的硬盤中杨帽，每個inode節(jié)點(diǎn)的大小為128字節(jié)漓穿，每1KB就設(shè)置一個inode，那么inode table的大小就會達(dá)到128MB注盈，占整塊硬盤的12.8%晃危。
查看每個硬盤分區(qū)的inode總數(shù)和已經(jīng)使用的數(shù)量，可以使用df命令。
df -i
查看每個inode節(jié)點(diǎn)的大小僚饭，可以用如下命令：
sudo dumpe2fs -h /dev/hda | grep "Inode size"
[圖片上傳失敗...(image-104db2-1513223980155)]
由于每個文件都必須有一個inode震叮，因此有可能發(fā)生inode已經(jīng)用光，但是硬盤還未存滿的情況鳍鸵。這時苇瓣，就無法在硬盤上創(chuàng)建新文件。
四偿乖、inode號碼
每個inode都有一個號碼击罪，操作系統(tǒng)用inode號碼來識別不同的文件。
這里值得重復(fù)一遍贪薪，Unix/Linux系統(tǒng)內(nèi)部不使用文件名媳禁，而使用inode號碼來識別文件。對于系統(tǒng)來說画切，文件名只是inode號碼便于識別的別稱或者綽號竣稽。
表面上，用戶通過文件名霍弹，打開文件丧枪。實際上，系統(tǒng)內(nèi)部這個過程分成三步：首先庞萍，系統(tǒng)找到這個文件名對應(yīng)的inode號碼拧烦；其次，通過inode號碼钝计，獲取inode信息恋博；最后，根據(jù)inode信息私恬，找到文件數(shù)據(jù)所在的block债沮，讀出數(shù)據(jù)。
使用ls -i命令本鸣，可以看到文件名對應(yīng)的inode號碼：
ls -i example.txt
五疫衩、目錄文件
Unix/Linux系統(tǒng)中，目錄（directory）也是一種文件荣德。打開目錄闷煤，實際上就是打開目錄文件。
目錄文件的結(jié)構(gòu)非常簡單涮瞻，就是一系列目錄項（dirent）的列表鲤拿。每個目錄項，由兩部分組成：所包含文件的文件名署咽，以及該文件名對應(yīng)的inode號碼近顷。
ls -i命令列出整個目錄文件，即文件名和inode號碼：
ls -i /etc
如果要查看文件的詳細(xì)信息，就必須根據(jù)inode號碼窒升，訪問inode節(jié)點(diǎn)缀遍，讀取信息。ls -l命令列出文件的詳細(xì)信息饱须。
ls -l /etc
理解了上面這些知識瑟由，就能理解目錄的權(quán)限。目錄文件的讀權(quán)限（r）和寫權(quán)限（w）冤寿，都是針對目錄文件本身歹苦。由于目錄文件內(nèi)只有文件名和inode號碼，所以如果只有讀權(quán)限督怜，只能獲取文件名殴瘦，無法獲取其他信息，因為其他信息都儲存在inode節(jié)點(diǎn)中号杠，而讀取inode節(jié)點(diǎn)內(nèi)的信息需要目錄文件的執(zhí)行權(quán)限（x）蚪腋。
六、硬鏈接
一般情況下姨蟋，文件名和inode號碼是"一一對應(yīng)"關(guān)系屉凯，每個inode號碼對應(yīng)一個文件名。但是眼溶，Unix/Linux系統(tǒng)允許悠砚，多個文件名指向同一個inode號碼。
這意味著堂飞，可以用不同的文件名訪問同樣的內(nèi)容灌旧；對文件內(nèi)容進(jìn)行修改，會影響到所有文件名绰筛；但是枢泰，刪除一個文件名，不影響另一個文件名的訪問铝噩。這種情況就被稱為"硬鏈接"（hard link）衡蚂。
ln命令可以創(chuàng)建硬鏈接：
ln 源文件 目標(biāo)文件
運(yùn)行上面這條命令以后，源文件與目標(biāo)文件的inode號碼相同骏庸，都指向同一個inode毛甲。inode信息中有一項叫做"鏈接數(shù)"，記錄指向該inode的文件名總數(shù)敞恋，這時就會增加1丽啡。
反過來谋右，刪除一個文件名硬猫，就會使得inode節(jié)點(diǎn)中的"鏈接數(shù)"減1。當(dāng)這個值減到0，表明沒有文件名指向這個inode啸蜜，系統(tǒng)就會回收這個inode號碼坑雅，以及其所對應(yīng)block區(qū)域。
這里順便說一下目錄文件的"鏈接數(shù)"衬横。創(chuàng)建目錄時裹粤，默認(rèn)會生成兩個目錄項："."和".."。前者的inode號碼就是當(dāng)前目錄的inode號碼蜂林，等同于當(dāng)前目錄的"硬鏈接"遥诉；后者的inode號碼就是當(dāng)前目錄的父目錄的inode號碼，等同于父目錄的"硬鏈接"噪叙。所以矮锈，任何一個目錄的"硬鏈接"總數(shù)，總是等于2加上它的子目錄總數(shù)（含隱藏目錄）睁蕾。
七苞笨、軟鏈接
除了硬鏈接以外，還有一種特殊情況子眶。
文件A和文件B的inode號碼雖然不一樣瀑凝，但是文件A的內(nèi)容是文件B的路徑。讀取文件A時臭杰，系統(tǒng)會自動將訪問者導(dǎo)向文件B粤咪。因此，無論打開哪一個文件渴杆，最終讀取的都是文件B射窒。這時，文件A就稱為文件B的"軟鏈接"（soft link）或者"符號鏈接（symbolic link）将塑。
這意味著脉顿，文件A依賴于文件B而存在，如果刪除了文件B点寥，打開文件A就會報錯："No such file or directory"艾疟。這是軟鏈接與硬鏈接最大的不同：文件A指向文件B的文件名，而不是文件B的inode號碼敢辩，文件B的inode"鏈接數(shù)"不會因此發(fā)生變化蔽莱。
ln -s命令可以創(chuàng)建軟鏈接。
ln -s 源文文件或目錄 目標(biāo)文件或目錄
八戚长、inode的特殊作用
由于inode號碼與文件名分離盗冷，這種機(jī)制導(dǎo)致了一些Unix/Linux系統(tǒng)特有的現(xiàn)象。
1. 有時同廉，文件名包含特殊字符仪糖，無法正常刪除柑司。這時，直接刪除inode節(jié)點(diǎn)锅劝，就能起到刪除文件的作用攒驰。
2. 移動文件或重命名文件，只是改變文件名故爵，不影響inode號碼玻粪。
3. 打開一個文件以后，系統(tǒng)就以inode號碼來識別這個文件诬垂，不再考慮文件名劲室。因此，通常來說结窘，系統(tǒng)無法從inode號碼得知文件名痹籍。
第3點(diǎn)使得軟件更新變得簡單，可以在不關(guān)閉軟件的情況下進(jìn)行更新晦鞋，不需要重啟蹲缠。因為系統(tǒng)通過inode號碼，識別運(yùn)行中的文件悠垛，不通過文件名线定。更新的時候攻谁，新版文件以同樣的文件名贫导，生成一個新的inode帖渠，不會影響到運(yùn)行中的文件篡殷。等到下一次運(yùn)行這個軟件的時候，文件名就自動指向新版文件侮邀，舊版文件的inode則被回收语盈。
