Linux內核(源代碼的鏈接在github)
Linux內核(源代碼的鏈接在github)
1.鏈表、雙向鏈表、無鎖鏈表。
2.B+ 樹，這是一些你無法在教科書上找到的說明。
一個相對簡單的B+樹的實現。我把它作為一個學習練習來幫助理解B+樹是如何工作的。這同樣也被證明是有用的。
...
一個在教科書中並不常見的技巧。最小的值在右側而不是在左側。所有在一個節點裡用到的槽都在左側，所有沒有用到的槽包含了空值(NUL)。大多數操作只簡單地遍歷所有的槽一次並在第一個空值時(NUL)終止。
3.優先排序列表 用於 互斥量、驅動等等。
Linux內核(源代碼的鏈接在github)
1.鏈表、雙向鏈表、無鎖鏈表。
2.B+ 樹，這是一些你無法在教科書上找到的說明。
一個相對簡單的B+樹的實現。我把它作為一個學習練習來幫助理解B+樹是如何工作的。這同樣也被證明是有用的。
...
一個在教科書中並不常見的技巧。最小的值在右側而不是在左側。所有在一個節點裡用到的槽都在左側，所有沒有用到的槽包含了空值(NUL)。大多數操作只簡單地遍歷所有的槽一次並在第一個空值時(NUL)終止。
3.優先排序列表 用於 互斥量、驅動等等。
4.紅黑樹用於調度、虛擬內存管理、追蹤文件描述符和目錄項等。
5.區間樹
6.根樹用於內存管理，NFS相關查詢和網絡相關功能。
根樹的一個通用的用處是存儲指針到結構頁中。
7.優先級堆，如其名稱的教科書實現，用於cgroup。
Linux內核(源代碼的鏈接在github)
1.鏈表、雙向鏈表、無鎖鏈表。
2.B+ 樹，這是一些你無法在教科書上找到的說明。
一個相對簡單的B+樹的實現。我把它作為一個學習練習來幫助理解B+樹是如何工作的。這同樣也被證明是有用的。
...
一個在教科書中並不常見的技巧。最小的值在右側而不是在左側。所有在一個節點裡用到的槽都在左側，所有沒有用到的槽包含了空值(NUL)。大多數操作只簡單地遍歷所有的槽一次並在第一個空值時(NUL)終止。
3.優先排序列表 用於 互斥量、驅動等等。
4.紅黑樹用於調度、虛擬內存管理、追蹤文件描述符和目錄項等。
5.區間樹
6.根樹用於內存管理，NFS相關查詢和網絡相關功能。
根樹的一個通用的用處是存儲指針到結構頁中。
7.優先級堆，如其名稱的教科書實現，用於cgroup。
8.哈希函數，參考了Knuth和一篇論文。
Knuth建議，用乘法哈希的機器字來表示接近黃金比例的素數的最大整數。Chuck Lever驗證了該技術的有效性：
http://www.citi.umich.edu/techreports/reports/citi-tr-00-1.pdf
這些素數的選擇是位稀疏的，他們可以通過移位和加法操作，而不必使用乘法器，乘法器是很慢的。
9.有的代碼，比如lov_pool這個驅動，實現了他們自己的哈希函數。
使用了一種旋轉哈希算法的哈希函數
Knuth, D. 《計算機程序設計藝術, 卷 3: 排序與搜索》, 第6、7章. Addison Wesley, 1973
10.哈希表用於實現inode、文件系統完整性檢測等等。
11.位數組用於處理標誌位、中斷等等。並在Knuth那本書的卷4中闡述。
12.信號量和自旋鎖
13.二分查找用於中斷處理,寄存器緩存查詢等等。
14.B樹的二分查找。
15.深度優先搜索被廣泛地用於目錄配置中。
執行一個修改過的命名空間樹的深度優先遍歷，以指定的start_handle節點開始（及結束）。回調函數會在任何一個參數匹配的節點被發現時被調用。如果回調函數返回了一個非0值，搜索將會立即終止並且將其返回給調用者。
16.廣度優先搜索用於檢測運行時鎖定的正確性。
17.鏈表中的歸併排序用於垃圾收集、文件系統管理等等。
18.冒泡排序在一個驅動庫中也有一個令人驚訝的實現。
19.Knuth-Morris-Pratt 字符串匹配,
根據Knuth、Morris和Pratt[1]實現了一個線性時間的字符串匹配算法。他們的算法避免了轉換函數的顯式地計算DELTA。對於長度為n的文本，其匹配時間是O(n)，對於長度為m的模式(pattern)，僅使用一個輔助函數PI[1 . .m]，預先計算模式的時間為O(m)。數組PI允許轉換函數DELTA被實時有效地計算。粗略地說，對於任何狀態"q"= 0,1,…、m和在SIGMA中的任何字符"a",PI["q"]的值包含的信息是獨立的"a"並需要計算DELTA("q","a") [2]。既然PI只有m個記錄，而DELTA有O(m |SIGMA|)個記錄，在預處理時間計算PI而不是DELTA的時候，我們可以節省一個因數|SIGMA|
[1] Cormen, Leiserson, Rivest, Stein，算法介紹，第二版，MIT出版社
[2] 見有限自動機原理
20.Boyer-Moore 模式匹配是在找替代品時的參考和建議。
實現了Boyer-Moore字符串匹配算法:
[1] 《一個快速的字符串搜索算法》，R.S. Boyer and Moore.計算機通信協會，20(10), 1977, pp. 762-772. http://www.cs.utexas.edu/users/moore/publications/fstrpos.pdf
[2] 《準確的字符串匹配算法手冊》，Thierry Lecroq, 2004 http://www-igm.univ-mlv.fr/~lecroq/string/string.pdf
注:由於Boyer-Moore(BM)從右到左搜索匹配，仍然有可能匹配分佈在多個塊，在這種情況下該算法並沒有優勢。
如果你希望確保這樣的事情永遠不會發生，那使用Knuth-Pratt-Morris(KMP)實現。總之，根據您的設置適當地選擇字符串搜索算法。
如果你正在用文本搜索器進行過濾，NIDS或任何類似的注重安全的目的，那麼使用KMP。否則，如果你真的關心性能，並且你對數據包進行分類以使用服務質量(QoS)政策，當你不介意匹配可能分佈分散，那麼用BM。