深度科技的anything快速檢索技術研究

張木梁 張 磊 秦 娣

1(武漢深之度科技有限公司技術部 北京 100080) 2(武漢深之度科技有限公司研發中心 北京 100080) 3(武漢深之度科技有限公司市場部 北京 100080) (zhangmuliang@deepin.com)

為了能夠向用戶提供一個高速的、基于文件名搜索的離線文件搜索功能，我們引入了“anything快速檢索”技術.對于“anything”的定義是Something like everything, but nothing is really like anything….

而anything之所以叫anything，是受到了Windows下everything軟件的啟發[1].原來在Linux中有一個類似的rlocate程序[2]，但是那個程序有點太老了，效率低下，效率方面的設計與當前時代不相稱.主要是出于與Linux傳統桌面結合得比較緊密，優化起來對系統其他組件影響都很大，很多發行版就不會在這方面進行優化.

1 基礎索引設計

1.1 簡要分析

在Linux下，最常用的文件搜索軟件是find，它會遞歸遍歷每個目錄，針對每個目錄與文件按照用戶給出的參數過濾出符合條件的目錄與文件，并打印出來.

在命令行模式下，find使用很廣，功能強大，不僅可以根據文件名查找文件，還可以根據文件類型、權限、修改時間、大小，甚至與其他軟件配合對文件進行過濾.但是在圖形界面下，用戶最常用的仍是根據文件名對文件進行查找，這是anything面向的核心問題.

使用find搜索時，如果已經搜索過，則對應的文件與目錄信息將會被緩存在內存中，可以大大加速搜索.當然，root用戶可以運行sysctl -w vm.drop_caches=3來清除這些緩存.但是，即使使用了緩存，在僅使用文件名搜索的前提下，find的搜索速度仍然是不理想的.

find搜索會通過系統調用遍歷每個目錄的內容，讀取其中的文件列表，再根據文件列表中的inode號找到對應的inode信息，接著讀取inode類型為目錄中的文件內容……如此遞歸查找.可以看到這個查找過程經過多重遞歸，會不斷打開目錄(需要系統調用與內存復制)，而且文件名在其中與inode信息夾雜在一起，會嚴重減緩純粹基于文件名的查找[3].

anything設計是與find完全不同的，不同之處在其內部僅保存了文件(目錄)名以及必要的歸屬關系，以便進行雙向的查找.所有的數據都存放在用戶態空間，沒有額外的系統調用開銷與內存復制開銷.此外，考慮到數據訪問的最大可能性，相鄰數據是最有可能被一起訪問的數據，因此anything可以最大限度利用處理器的高速緩存，使得軟件的運行性能更好.

總的來說，anything的設計理論上快速的主要原因是：

1) 相比于find，它不依賴于額外的系統調用與函數調用，減少了大量的系統調用開銷與內存復制開銷；

2) 它使用的文件系統存儲結構的設計針對性極強，內容非常緊湊，使用也很高效.

1.2 內部存儲設計

在經典設計中，文件系統應該使用數據結構中的樹來存儲.樹中的每個節點有一個字符串作為名稱，有N個指針指向其N個子節點，還有一個指針指向其父節點，以支持從上至下以及從下至上的雙向樹遍歷.這種結構的優點是修改很方便，不管是刪除、添加還是重命名每個節點都很快.但是在遍歷讀取時卻因為需要不停的指針跳轉，會導致處理器的高速緩存頻頻失效，從而使得訪問速度降低，而又因為各個節點都是分散的，無法體現出相鄰節點的訪問相關性，所以也難以進行有效的內存訪問優化.

下面是上述樹型設計數據結構內存消耗的分析.為簡單起見，先假設文件系統是一棵深度為D、分叉為N(N>1)的完全樹，這樣，在整棵樹中一共有葉節點ND-1個、非葉節點N0+N1+N2+…+ND-2=(ND-1-1)(N-1)個.對于每個葉節點而言，忽略其文件名，其他部分的內存僅包括一個指向其自身上一級的指針；對于每個非葉節點而言，忽略其文件名，其他部分的內存也包含一個指向其自身上一級的指針(假設根節點也有一個父節點指針，但是其值為空)，以及N個指向子節點的指針，指針數一共是P=ND-1+(N+1)(ND-1-1)(N-1)=(2×ND-N-1)(N-1)個，對于64 b系統而言，需要的內存是8×P個字節.

在anything內部存儲結構設計的早期階段，使用樹來保存文件系統結構也曾被考慮過，但是顧及高速緩存失效與指針過大的問題，顯然在此處使用線性存儲設計更好.所以就有了下面anything的數據結構來保存文件系統數據的內部存儲結構.

從表1可以看出，anything內部文件系統存儲頭部為4 B的MAGIC和4 B的緩存區，之所以使用4 B，而不是64 b系統上的8 B是因為對于1 000萬個文件與目錄的文件系統而言，使用上述結構僅需約250 MB內存，因此不需要8 B的長度與偏移量，從而可以節約一半的指針長度.在8 B之后是一個C語言風格的字符串，對應的是此文件系統樹的根目錄名，例如“”或者“homedeepin”，這個根目錄要求“”開頭，“”結尾，整個字符串以空字符結尾.

表1 anything的數據結構

在上述頭部數據之后即為正式的文件樹結構，每個文件或者目錄名均是一個C語言風格的、以空字符結尾的字符串.表1中大寫的TAG標簽代表一個目錄的結束，并且包含了自身父目錄節點的偏移量；小寫的tag標簽代表一個文件信息的結束，并且以標簽長度代表自身是文件還是目錄.在每個字符串之后是一個標簽(tag)，對于文件來說，此標簽占據1 B，標識這是一個文件.對于目錄而言，此標簽占據4 B，標識這是一個目錄，而且記錄了這個目錄中第1個文件的偏移量，按照之前的分析，這個偏移量僅需要4 B就夠了，通過目錄的這個4 B標簽就可以向下遍歷.如此反復，直到此目錄結束，將是一個單獨的值為0的字節，其后又是一個4 B的標簽(TAG)，此標簽除了標識目錄結束之外，還記錄了本級目錄的父節點的偏移量，如此，就可以通過這個標簽支持向上遍歷.此外，當本級目錄結束之后將開始下級目錄的存儲，這樣即可以使得1棵目錄樹的數據是緊緊相鄰的，在讀取時非常高效，在刪除時也非常方便.

上述結構不斷重復，直到整個文件樹結束.

由上述結構可以看出，相鄰的節點，即同級目錄下的文件都存儲在一起，這樣有利于內存訪問優化.而且將8 B指針優化為4 B偏移量，也節省了存儲空間，減少了無效數據的存儲與無效內存的訪問，此外，線性存儲也便于數據文件的存盤與讀盤.

對于每個葉節點，需要耗費1 B存儲標簽，對于每個非葉節點需要消耗4 B存儲子節點的偏移量，還有4 B用來存儲其所有子節點指向其本身的偏移量，則一共需要ND-1+8×(ND-1-1)(N-1)=(ND+7×ND-1-8)(N-1)個字節，對比之前樹需要耗費的8×P=8×(2×ND-N-1)(N-1)個字節，易知在最好情況下是其內存的116，在最差情況下是其內存的13.

當使用此結構進行搜索時不需要再通過樹狀搜索，而可以使用線性搜索，從前至后進行字符串匹配，并跳過數據量較小的標簽即可，這樣也方便進行搜索分頁.

當搜索到某個名稱符合要求時，即可使用目錄結尾的標簽定位到父目錄的偏移量，繼而構成完整的路徑，返回給調用者.

在這里也可以發現，其實對于搜索而言，程序并不需要保存子節點的偏移量，只需要父節點的偏移量即可，這樣還可以把額外的內存再節省約一半，但是這會導致文件系統更改(文件與目錄刪除、添加、重命名)時變更速度較慢.若僅需使用離線搜索，即不考慮文件系統改動的問題，則內存消耗確實還可通過使用上述方法進一步減少.

此外，由于需要至少1位來標識文件或者目錄，因此最大的偏移量不可能是232，即最多能存儲231或2 GB內存的數據.為了可擴展性考慮，在內部其實保留了2位數據以進行文件標識，因此，最多可以使用1 GB內存作為內部存儲.根據之前的測試估算，大約能保存4 000萬個文件或目錄，在目前看來是足夠的.

1.3 理論對比與實際測試

在進行實際測試驗證之前，首先作理論對比.

在預估為包含38.7萬個文件(目錄)、其中有大約4萬個目錄的情況下：

2) 若使用樹進行數據存儲與搜索，在遍歷過程中需要持續生成節點，在搜索過程中需要遞歸遍歷(遞歸函數調用)各個節點，然后對每個節點調用strstr函數，即需要有4萬次遞歸函數調用以及38.7萬次strstr函數調用.當然，在此期間高速緩存也會頻頻失效.在搜索過程中，由于不再需要系統調用，以及額外的從內核態到用戶態的內存復制(這個開銷相對較小)，這種搜索方法應該會至少比find快一個數量級.

3) 使用anything也首先需要進行目錄樹遍歷，但是在搜索過程中需要從前向后，反復在線性存儲空間中調用strstr即可，即大約需要38.7萬次strstr調用.沒有系統調用開銷，沒有內存復制開銷，而且由于內存緊湊，又是單向內存順序訪問，因此內存訪問進入高速緩存浪費極少，非常自然，使用也很流暢，比目錄樹狀遞歸跳轉顯然要高效很多.

可以看出，從理論設計來看，anything的效率要明顯優于前2種設計方案.

為了進一步確定上述猜測是否正確，我們開發了3個程序來實際驗證我們的理論設計.

程序2：遍歷目錄時建立樹狀結構后，再基于內存樹存儲進行搜索.

程序3：遍歷目錄時構建基礎索引完成后，再基于基礎索引進行搜索.

這3個程序的關鍵源碼分別參見程序1～3.

程序1. 遞歸遍歷直接搜索文件名.

void walkdir (const char* path, const char* query, int* count)

{

DIR* dir=opendir(path);

if (0==dir)

return;

struct dirent* de=0;

while ((de=readdir(dir))!=0) {

if (strcmp(de->d_name, ″.″)==0‖strcmp(de->d_name, ″..″)==0)

continue;

if (de->d_type!=DT_DIR &&

de->d_type!=DT_REG &&

de->d_type!=DT_LNK)

continue;

if (strstr(de->d_name, query)!=0) {

if (*count<10)

*count, path, de->d_name);

*count=*count+1;

}

if (de->d_type==DT_DIR) {

char fullpath[PATH_MAX];

de->d_name);

walkdir(fullpath, query, count);

}

}

closedir(dir);

}

程序2. 遞歸遍歷建立樹后再搜索.

typedef struct __fs_tree_item__ {

char* name;

int kids_count;

struct __fs_tree_item__* parent;

struct __fs_tree_item__** kids;

} fs_tree_item;

void walkdir(const char* path, fs_tree_item* fti)

{

DIR* dir=opendir(path);

if (0==dir)

return;

struct dirent* de=0;

while ((de=readdir(dir))!=0) {

if (strcmp(de->d_name, ″.″)==0‖strcmp(de->d_name, ″..″)==0)

continue;

if (de->d_type!=DT_DIR && de->

d_type!=DT_REG && de->d_type

!=DT_LNK)

continue;

fs_tree_item*kid=calloc(1, sizeof(

fs_tree_item));

if (kid==0) {

printf(″kid malloc error, path: %s,

name: %s, count: %d ″, path,

de->d_name, fti->kids_count);

continue;

}

kid->name=strdup(de->d_name);

if (kid->name==0) {

free(kid);

printf(″kid strdup error, path: %s,

name: %s, count: %d ″, path,

de->d_name, fti->kids_count);

continue;

}

kid->parent=fti;

fs_tree_item** kids=realloc(

fti->kids, (fti->kids_count+1)*

sizeof(void*));

if (kids==0) {

free(kid->name);

free(kid);

printf(″kids realloc error, path: %s,

name: %s, count: %d ″, path,

de->d_name, fti->kids_count);

continue;

}

fti->kids=kids;

fti->kids[fti->kids_count]=kid;

fti->kids_count++;

if (de->d_type==DT_DIR) {

char fullpath[PATH_MAX];

de->d_name);

walkdir(fullpath, kid);

}

}

closedir(dir);

}

void search_tree(const char* path, fs_tree_item* root, const char* query, int* count)

{

if (strstr(root->name, query)!=0) {

if (*count<10)

path, root->name);

*count=*count+1;

}

char fullpath[PATH_MAX];

root->name);

for (int i=0;ikids_count;i++)

search_tree(fullpath, root->kids[i],

query, count);

}

程序3. 遞歸遍歷構建好基礎索引后再搜索 (需使用anything庫與頭文件).

static int walkdir(const char* name, fs_buf* fsbuf, uint32_t parent_off)

{

DIR* dir=opendir(name);

if (0==dir)

return EMPTY_DIR;

uint32_t start=get_tail(fsbuf);

struct dirent* de=0;

while ((de=readdir(dir))!=0) {

if (strcmp(de->d_name, ″.″)==0‖strcmp(de->d_name, ″..″)==0)

continue;

if (de->d_type!=DT_DIR &&

de->d_type!=DT_REG &&

de->d_type!=DT_LNK)

continue;

append_new_name(fsbuf, de->

d_name, de->d_type==

DT_DIR);

}

closedir(dir);

if (start==get_tail(fsbuf))

return EMPTY_DIR;

uint32_t end=get_tail(fsbuf);

append_parent(fsbuf, parent_off);

uint32_t off=start;

while (off

if (is_file(fsbuf, off)) {

off=next_name(fsbuf, off);

continue;

}

set_kids_off(fsbuf, off, get_tail(fsbuf));

char path[PATH_MAX];

get_name(fsbuf, off));

if (walkdir(path, fsbuf, off)==

EMPTY_DIR)

set_kids_off(fsbuf, off, 0);

off=next_name(fsbuf, off);

}

return NONEMPTY_DIR;

}

#define MAX_RESULTS 10

static uint32_t search_by_fsbuf(fs_buf*fsbuf, const char* query)

{

uint32_t name_offs[MAX_RESULTS], end_off=get_tail(fsbuf);

uint32_t count=MAX_RESULTS,

start_off=first_name(fsbuf);

search_files(fsbuf, &start_off, end_off,

query, name_offs, &count);

char path[PATH_MAX];

for (uint32_t i=0; i

char *p=get_path_by_name_off(fsbuf,

name_offs[i], path, sizeof(path));

printf(″%’u: %c %s ″, i+1, is_file(fsbuf, name_offs[i]) ? ′F′ : ′D′, p);

}

uint32_t total=count;

while(count==MAX_RESULTS) {

search_files(fsbuf,&start_off, end_off, query, name_offs,&count);

total+=count;

}

return total;

}

在程序里單獨在搜索前后調用gettimeofday獲取時間戳，進行差分比較，在有緩存的情況下，3種方法搜索的耗時分別為：

1) 邊遞歸遍歷目錄邊匹配(類find)，10.1 s；

2) 遞歸遍歷目錄后用樹存儲目錄結構再搜索，77 ms；

3) 遞歸遍歷目錄后用基礎索引存儲目錄結構再搜索，8 ms.

如果使用perf,strace與google perftools進行性能剖析，可以看出在第1個程序里主要的程序耗時(88%)都花在了opendir()的調用上.第2、第3個程序在搜索階段運行沒有與內核交互，而且時間過短，采樣過少，因此沒有有意義的數據產生，但是可以看出使用基礎索引技術比使用樹的方法快了接近10倍.

2 二級索引設計

上述基礎索引的設計已經大大提高了基于文件名的搜索速度(相對于find而言)，但這種搜索方法仍然需要從前至后遍歷每個文件名進行搜索[4].從表面上看，因為需要對每個文件名進行檢查，以得知其是否匹配搜索串，理論上不會有更快的方法了.但事實上，我們還可以做得更好，那就是使用倒排索引(inverted index)實現二級索引.

倒排索引的原理是對目標字符串進行切割，得到其所有的子字符串，然后將這些子字符串存放到對應的索引數據結構中，當用戶輸入對應的子字符串時能立刻找到相應的原始字符串[5].

例如原始字符串為china，則可以得到c,h,i,n,a,ch,hi,in,na,chi,hin,ina,chin,hina與china，一共5+4+3+2+1=15個子字符串，假設china這個字符串的偏移量(或者指針)是100，則可以得到{“c”→100}, {“h”→100}, …, {“china”→100}等25個索引.當用戶輸入hi時，即可以立刻得到{“hi”→100}這個索引，然后將100返回給調用者，由調用者通過這個偏移量或者指針得到“china”這個字符串.

在簡單的倒排索引設計中，一般使用Hash鏈表或者Trie樹作為索引數據結構[6].anything使用的是Hash鏈表，其工作原理是，當用戶輸入某個查詢字符串(如hi)時，anything將首先對字符串進行一次Hash運算，得到Hash數組中的下標值，然后根據下標值即可得到對應的索引數組，在索引數組里順序查找即可得到對應的索引(即hi)，從而可以獲取到所有的包含hi字符串的原始字符串的偏移量，將其返回給調用者.

對于38.7萬個文件與目錄遍歷的實測表明，其索引內存占用將超過2 GB，這完全是不可接受的.而對anything在對二級索引進行優化后，內存消耗可以大幅度減少.在對上述含有38.7萬個文件與目錄的遍歷表明，其索引大約有600萬個，索引占用內存約230 MB，程序占據內存不超過500 MB(因為動態內存分配需要大量的額外內存空間)，基本可以接受.

在基礎索引中，如果是38.7萬文件與目錄，則一共需要進行38.7萬次strstr的調用以完成一次完整的查找.在二級索引中，如果使用了Hash鏈表，每次查找時就可以大大減少strcmp的次數.在這里，anything采用了質數模的方法作為Hash函數.對比基礎索引搜索需要的38.7萬個strstr調用，可以提高數10倍的性能.

測試環境中4個搜索方法的對比如下：

1) find——10.1 s，系統緩存增加260 MB;

2) 樹搜索——77 ms，存儲數據內存需要30 MB;

3) 基礎索引搜索——8 ms，存儲數據程序內存需要7 MB;

4) 二級索引搜索——0.4 ms，存儲數據程序內存需要230 MB.

當然，二級索引的問題仍然是其占用內存實在太大，對于38.7萬個文件與目錄的文件數來說，基礎索引約占用7 MB內存，而二級索引則需要占用約230 MB內存.其次，當發生文件系統變更時，基礎索引的變更比較容易實現，但是二級索引的更新就相當繁復了，需要遍歷所有的索引，找到對應的原始字符串偏移量進行修改.此外，二級索引的文件保存與載入也較為麻煩，因為需要將整個Hash鏈表序列化與反序列化，而且當文件系統變更時，一旦變更了索引，則需要進行數百兆甚至上吉數據的重新序列化，也會增大磁盤壓力.

因此，除非是在對文件名搜索速度非常關鍵的場所或者離線搜索的場景下，不然使用基礎索引進行文件名搜索即可滿足要求.這將是anything應用于其他場景的擴展能力，不在本文介紹.

3 文件系統監控

從以上可以看出，搜索提速最重要的原因是省去系統調用，但是文件系統是會不停變化的.因此anything需要對文件系統進行監控，在變化時及時對內部的基礎索引進行修改才能保證搜索的正確性與實時性.

everything對于文件系統變更的追蹤相對簡單一些，因為它直接依賴于Windows下NTFS文件系統的日志[7].但是在Linux下，首先文件系統繁多，例如RHEL 7CentOS 7采用的缺省文件系統是XFS，但是Debian與RHEL 6CentOS 6使用的缺省文件系統卻是ext4，而且這兩者的文件系統日志都沒有NTFS信息完全[8].除此之外還有btrfs等一系列的其他文件系統.其次是在Linux下，管理員或者用戶對于文件系統的選擇較多，并且可以深入調整文件系統的參數，例如去掉日志，因此僅依賴于文件系統日志檢查文件系統的變更是不太可靠的.

另外，由于Linux本身沒有全局的文件創建、刪除與重命名的用戶態接口(比較接近的inotify無法遞歸監控目錄)[9]，因此要解決此問題，只能使用獨立的模塊監聽文件的創建、刪除與重命名，并通知相應的用戶態程序更新文件系統數據與索引數據.

在Linux下，監控整個文件系統的變化可以采用下列方法：

1) 使用preload庫，監控glibc對應函數的參數與返回值，包括open,fopen,creat,mkdir,rmdir,rename等.這種方式的優點是不依賴于內核，但是它會對所有依賴于glibc庫的程序都造成影響，影響面大，工作量也不小(函數較多，參數處理較多)，而且具有較大的安全隱患，此外，對于靜態編譯libc庫的程序以及不依賴于libc庫的程序(雖然這種程序很少)無法監控.

2) 使用審計系統，加入對相應系統調用(open,creat,mkdir等)的審計，通過審計日志檢查系統調用的結果，根據結果更新文件系統數據.其優點是不依賴于內核，系統調用數量較少，但是缺點是需要依賴于審計系統，而且事后處理日志的方式會缺少關鍵的場景信息，例如之前的文件或者目錄是否存在.

4) 編寫內核模塊，使用內核熱補丁技術(livepatch)替換內核函數.與上述技術路線類似，不需要自己考慮替換內核函數指針的問題，缺點是需要重新實現或者調用原始函數，以保證功能的正確，而且熱補丁技術對內核特性要求較高，龍芯申威內核現在并沒有實現相應的功能.此外，如果相應的函數由于出現了問題需要使用熱補丁修復，將會帶來一些維護上的問題，雖然可能性較小.

5) 編寫內核模塊，使用內核tracepoint特性對系統調用入口與出口進行事件跟蹤，并記錄處理結果，缺點是會對所有的系統調用進行跟蹤，因此需要自己過濾，而且系統調用路徑較長，可能會導致較多的資源占用.

6) 編寫內核模塊，通過kprobes對內核函數進行掛鉤，在函數入口和出口處進行參數與返回值的檢查，當發現滿足要求的文件事件時將事件信息記錄下來，其缺點是對比tracepoint來說，kprobes從理論上依賴的函數變化的可能性更大一些，當內核升級時可能會帶來維護的問題[10].

anything選擇了最后一種解決方法，雖然它要求內核支持kprobes特性，但這是一個較容易實現的特性，而且anything要監控的內核函數也相對穩定.

具體到需要跟蹤的內核函數，主要就是VFS的文件系統變更函數，包括vfs_create等.為了確保只有當函數成功返回時才進行記錄，anything需要使用kretprobes進行函數跟蹤.

需要注意的是，使用kretprobes有一個與架構相關的問題，那就是要在函數入口處得到函數各參數的值，而在這里，kretprobes沒有給開發者提供很多便利，需要根據不同CPU架構的內核寄存器結構體(pt_regs)制定的函數調用規約才能獲取相關的參數值.例如對于X86來說，其64 b系統的函數調用規約是從第1個參數開始，分別使用rdi,rsi,rdx,rcx,r8與r9寄存器保存參數，從第7個參數開始使用棧來保存剩余的參數.這些代碼都被封裝到源碼的kernelmodarg_extractor.c中.因此，當需要擴展架構支持時，主要在這里進行修改即可.此外，在實際使用中，anything現在僅用到前4個參數，因此只要處理n等于1～4的情況即可.

4 測試驗證與結論

本文使用一個簡單但仍有典型意義的文件搜索來完成以下對比測試：

首先是測試環境.測試環境物理機為ThinkPad x230(8 GB內存+機械硬盤).虛擬機為運行在VirtualBox里完整安裝的Deepin 15.4(分配虛擬單核處理器2.9 GHz，虛擬內存2 GB).

測試方法如下：

1) 使用sysctl -w vm.drop_caches=3清空緩存，然后運行find-name ″*hellfire*，耗時約39.9 s.

3) 使用anything的基礎索引搜索hellfire，耗時約6 ms，基礎索引占用內存約7 MB，測試程序占用內存約14 MB.

4) 使用anything的二級索引搜索hellfire，耗時0 ms，二級索引占用內存約230 MB，測試程序占用內存約500 MB.

通過多次測試的結果表明，使用基礎索引比使用帶緩存的find搜索要快大約500倍甚至更多.若在忽略內存等附加消耗的情況下，使用全內存式的二級索引，anything的搜索速度會比使用基礎索引搜索速度再快20倍以上(但是占用內存將增長35倍).是否引入二級索引需要根據實際的應用場景來取舍，這是典型的時間空間復雜度互換的問題.

在處理器支持上，已經驗證anything能完全支持X86和自主可控CPU平臺，包括龍芯和ARM處理器，支持較新的申威(對部分擴展指令集有要求).

anything是一個小巧的軟件，其功能很單一.但是它達到了為文件名搜索提供一個高效快速實現的目標，而且對現有的系統侵入很小.同時，anything開源，希望有興趣的人能為它提交補丁，特別是對其他文件系統以及架構的支持，當然也包括對程序本身的修正和改進.

[1]萬立夫. 讓Everything支持網盤目錄搜索[J]. 電腦迷: 技巧與實踐Software, 2012 (2): 77

[2]Rasto L. About rlocate官方文檔[OL]. [2017-12-15]. http://rlocate.sourceforge.net/

[3]Wbruce C, Donald M, Trevor S. 計算機科學叢書：搜索引擎信息檢索實踐[M]. 劉挺, 秦冰, 張宇, 等譯. 1版. 北京: 機械工業出版社, 2010

[4]周磊. 十五個經典算法研究與總結[OL]. [2017-12-15]. http://blog.csdn.net/v_JULY_v

[5]沈東良. Linux內核中鏈表和散列表的實現原理揭秘[OL]. [2017-12-15]. http://blog.csdn.net/shendl

[6]嚴浪. 倒排文件技術設計[J]. 計算機與數字工程, 2011 (3): 168-170

[7]Zhao J. 探索Everything背后的技術[OL]. [2017-12-15]. https://wenku.baidu.com/view/76bb29da80eb6294dd886cb7.html

[8]Harley Q. Linux和Windows的遍歷目錄下所有文件的方法[OL]. [2017-12-15]. https://www.cnblogs.com/Harley-Quinn/p/6367425.html

[9]Zhang S. Linux文件系統變化通知機制—inotify[OL]. [2017-12-15]. http://blog.csdn.net/zhangskd/article/details/7572320

[10]潘風云. Linux內核kprobe機制[OL]. [2017-12-15]. http://blog.csdn.net/panfengyun12345/article/details/19480567