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。
