知识卡片

普通读书笔记卡 · 3566.j

掩码限定基数树前缀

理解等级:中级

ngx_radix32tree_insert 用32位 key 的高位逐层选择左右分支,mask 指定有效前缀,决定停止的层数。同一个 key 在不同 mask 下代表不同前缀范围;查找时要按预期的最长匹配语义理解结果。发散:前缀索引定位的是“范围”,不能把它当完整整数相等比较。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    原书出处

    参考来源

    - 位置:《深入理解Nginx:模块开发与架构解析(第2版)》第7章7.6.1–7.6.3(源文件:`_epub-src/EPUB/text00058.html`,图7-9 `Image00075.jpg`);[Nginx 1.8.0 `ngx_radix_tree.c`](https://github.com/nginx/nginx/blob/release-1.8.0/src/core/ngx_radix_tree.c)。 - 结论依据:书中以前3位掩码解释0/1逐层选支,图7-9给出001、010、100、110前缀;对应版本源码的find沿路径保留最后一个有值节点,实现最长前缀匹配。此结论限定于书中32位API。 - 原始内容:掩码中为1的位节点关键字中有效的位数同时也决定了树的有效高度。