Linux 内核里的数据结构——基数树

基数树 （ Radix tree ）

正如你所知道的，Linux内核提供了许多不同的库和函数，它们实现了不同的数据结构和算法。在这部分，我们将研究其中一种数据结构—— 基数树 （ Radix tree ） 。在 Linux 内核中，有两个文件与基数树的实现和API相关：

• include/linux/radix-tree.h
• lib/radix-tree.c

让我们先说说什么是 基数树 吧。基数树是一种 压缩的字典树 （ compressed trie ） ，而字典树是实现了关联数组接口并允许以 键值对 方式存储值的一种数据结构。这里的键通常是字符串，但可以使用任意数据类型。字典树因为它的节点而与 n叉树 不同。字典树的节点不存储键，而是存储单个字符的标签。与一个给定节点关联的键可以通过从根遍历到该节点获得。举个例子：

               +--++
        |                         |
        |                         |
   +--v--+            +-v+            +--+
   |           |            |           |
   |    o      |            |     a     |
   |           |            |           |
   +--+
                                  |
                                  |
                            +--+
                            |           |
                            |     t     |
                            |           |
                            +

via: <https://github.com/0xAX/linux-insides/blob/master/DataStructures/radix-tree.md>

作者：[0xAX] 译者：[cposture](https://github.com/cposture) 校对：[Mr小眼儿](https://github.com/tinyeyeser)

本文由 [LCTT](https://github.com/LCTT/TranslateProject) 原创翻译，[Linux中国](http://linux.cn/) 荣誉推出