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

0xAX 的头像

·

·

·

11,529 次阅读

基数树 Radix tree

Trie

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

让我们先说说什么是 基数树 吧。基数树是一种 压缩的字典树 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/) 荣誉推出

2 条回复

  1. 来自浙江杭州浙江大学的 Maxthon 4.4|Windows 7 用户 的头像
    来自浙江杭州浙江大学的 Maxthon 4.4|Windows 7 用户

    赞!干货!

    来自杭州
  2. cicada [Chrome 54.0|Windows 7] 的头像
    cicada [Chrome 54.0|Windows 7]

    好好学习一下

    来自深圳

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注