知识卡片
掩码限定基数树前缀
ngx_radix32tree_insert 用32位 key 的高位逐层选择左右分支,mask 指定有效前缀,决定停止的层数。同一个 key 在不同 mask 下代表不同前缀范围;查找时要按预期的最长匹配语义理解结果。发散:前缀索引定位的是“范围”,不能把它当完整整数相等比较。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
原书出处
参考来源
- 位置:《深入理解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的位节点关键字中有效的位数同时也决定了树的有效高度。