下载掌阅APP，畅读海量书库
立即打开
Linux内核中实现了一个通用的B+树（btree.h），B+树大部分被用于文件系统中，一些文件系统也实现了自己的B+树。内核中还有radix tree用于将指针与long整数键值关联（例如IDR机制）。Linux基树与trie树非常类似，只是一个用来查询定位整数，一个用来定位字符串。
IDR（Integer ID Management）机制在Linux内核中指的是整数ID管理机制，即将一个整数ID号和一个指针关联在一起的机制。IDR机制最早在2003年2月加入内核，当时作为POSIX定时器的一个补丁。现在内核中很多地方都可以找到它的身影。
IDR机制适用于那些需要把某个整数和特定指针关联在一起的地方。例如在IIC总线中，每个设备都有自己的地址，要想在总线上找到特定的设备，就必须要先发送设备的地址。当适配器要访问总线上的IIC设备时，首先要知道它们的ID号，同时要在内核中建立一个用于描述该设备的结构体和驱动程序。将ID号和设备结构体结合起来，如果使用数组进行索引，一旦ID号很大，用数组索引则会占据大量的内存空间，这显然不可行。也可以用链表进行索引，但是如果总线中实际存在的设备很多，则链表的查询效率会很低。此时IDR机制应运而生，该机制内部采用radix tree实现，可以很方便地将整数和指针关联起来，并且具有很高的搜索效率。
FIFO文件是内核提供给用户空间的一个非常好用的工具，也叫作命名管道，其与KFIFO的内部机制并不一样，KFIFO的内部是一个简单的双向队列，FIFO文件相当于一个跨进程的队列，并且提供了原生的阻塞和配合文件能力的工具。例如你可以用select的BLOCK模式打开这样一个FIFO文件，同时设置超时，也可以用普通的read调用读取FIFO文件内容，这样FIFO在收到数据之前将永久阻塞。如果没有FIFO文件机制，则要使用消息队列实现同样的操作，或者使用UNIX domain socket进行模拟，后者更容易一些。然而FIFO文件还有一个特性，就是它首先是一个文件，即使没有人在读取，也可以往文件里写内容，这就带来了比socket更加强大的能力。但是在严肃的应用场景下，FIFO文件并不容易使用，要同时满足以下这些需求时才应该选用FIFO。
· 跨进程传输数据。
· 数据的产生和数据的监听不同步，并且希望产生数据的时候读取者即使没有读取也有缓存能力。
· 数据只要被读取了就会被删除，第二次就不会被再次读取。
· 需要等待超时、永久阻塞、立即返回中的某些或者全部特性。
· 需要运维系统查看数据流。
· 目前为止没有任何办法提前判断你要读的阻塞式的FIFO内是否有数据。
在Linux操作系统中，命名管道FIFO文件几乎是唯一一种同时满足以上需求的通信方式，但是绝大多数情况你仍然需要的是Unix Domain Socket，除非你需要随时查看或者截断通信过程中的数据流（便于调试和运维），或者是遇到了极限的性能问题（一般FIFO文件性能是最好的）。FIFO文件是不容易使用的。大部分人会使用FIFO文件的非阻塞模式，如果需要阻塞等待就调用select，并且设置timeout，然后在事件到来的时候反复调用read，直到数据读完。因为阻塞模式下select的timeout是没有效果的，文件句柄fd会一直处于可读状态。而阻塞模式只要读了就会一直阻塞，没有timeout。并且在阻塞模式下，如果你调用read读取了一定的长度，就永远不知道还有没有数据没有读取完，除非继续读取，然而如果这么做就会继续被堵塞。但并不是说用非阻塞的，使用select配合就可以高枕无忧了。当你select到有内容可以读，然后读取处理，再次调用select，在这期间如果没有读取到完整的数据，即使数据后续被写入到了FIFO文件中也读取不到，因为你在后续数据事件到达之后才调用了select。也就是说这种模型在单个消息比较大的情况下使用是有问题的，比较简单的方法是直接使用非阻塞遍历循环的查询。但是如此就很难平衡FIFO文件缓存大小和遍历频率的设计带来的CPU损耗。代码如下。
以上是一个可以block read的完整实现，这里的用处是每次读取一行数据返回。其中涉及这种读取要考虑的所有情况，可见使用其很不容易。
总体而言，读取文件分为监听式和轮询式。监听式看起来简单，但是在实际使用中有很多问题，通常需要借助线程进行辅助处理。类似socket接到一个连接就生成一个线程来处理的流程。而轮询式一般也是开一个线程去轮询，但是轮询一遍会睡眠，否则就会造成CPU占用过高。大部分情况下轮询的方式简单有效。
但是阻塞却是FIFO文件在交互式shell中非常有效的调试工具。mkfifo命令也能建立FIFO文件。在阻塞模式下，当cat的时候FIFO文件里面没有数据，命令行就会阻塞在那里，但是若有一方使用了echo等向其写入了数据，cat就会立即执行读取数据。FIFO文件对于交互式的调试在使用上是十分友好的。
在Linux中，管道并没有用专门的数据结构，而是通过将两个file结构指向同一个临时的VFS索引节点inode，而这个VFS索引节点又是指向一个物理页面而实现的。FIFO文件被称为命名管道，而PIPE则是不存在实际的文件系统中的文件，只有程序调用API的匿名管道。
FIFO和PIPE的最大缓存大小可以在/proc/sys/fs/pipe-max-size文件里修改和查看。并且当你使用shell的时候在ulimit里面还有一个pipe size的大小限制。即使使用命令行，在操作FIFO的时候也需要格外注意，比如要及时刷掉写入缓存。代码如下。
在写入FIFO文件的时候最好不要使用文件的缓存功能，要一次性地完整写入。
位数组叫作bitmap，是以位为单位存储值的方式。很多情况下一些值只有两个取值，而这些值又很多，就可以用位数组实现。也可以看成是bool类型的数组，但是bitmap提供了更多的相关操作，而这些操作很多都是实际使用bitmap数据结构的模块进行实际实现的。其定义非常简单：
位数组可以用来执行排序算法，利用的就是数组中的索引值，将某个索引值设置为1就表示记录，然后顺序输出索引值就是排序后的结果（桶排序）。更多的时候位数组在文件系统中充当位图。几乎大部分的文件系统都有位图的概念，例如ext2中就有inode位图和数据块位图，用来表示对应序号的inode或者数据块有没有被使用。在raid系统中，例如raid1的数据一致性保障，由于系统有两份拷贝，不一致的情况就有可能发生，当保证一致时就会设置对应的位图位，后续的更新就都是增量的，只需要查看位图就知道哪些是未能保证一致的数据了。