[友猫]NFD Developers Guide--Table（3）
8.NameTree
名字树是FIB，PIT，StretagyChioceTable,和Measurements table的通用索引结果，这样的通用是应为这四种表存在一些共性，FIB，StretagyChioceTable,和Measurements table都是一名字为索引，PIT则以名字和selector为索引。由于查询表的过程是相关的，因此可以通过Shortcuts来关联两个表，降低索引次数，同时降低存储消耗。
结构
名字树有名字树项组成，由名字索引。FIB，PIT，StretagyChioceTable,和Measurements table附加在名字树的项上。名字树项
一个项包含以下内容：
- 名字前缀
- 指向父节点指针
- 一系列指向子节点指针
- 零或一个FIB项
- 零或多个PIT项
- 零或一个StretagyChioce项
- 零或一个Measurements项
名字树通过父节点指针，字节点指针分为三个结构。FIB，StretagyChioceTable,和Measurements table附件到具有相同名字的名字树项，在大多数情况下PIT项可以附加到友相同名字的名字树项，不同之处只表现在selector。在一些特殊情况下，那些名字末尾友隐式摘要的PITxianghuui被附加那些对应兴趣包名字减去隐式摘要部分的名字树项。因此对于incoming data name 的全部匹配算法多可以找到这个PIT项。
NAMETREE hash table
除了三个结构，名字树还包含一个哈希表，以实现快速查询。对于所给的名字前缀，由其所对应的TLV计算哈希，同时哈希值与一个块进行映射。
哈希碰转则通过链接（chaining)解决：如果多个名字映射到统一个块，所有的项通过一个单链表(linkedlist)被链接到这个块。
随着名字树项的表化，哈希表自动的调整大小，通过自动调整呢操作，新的块的数量被计算，这个数量需要在空块容量和链接时间开销上进行权衡。此后每一个名字树项重新进行哈希计算，并在新的哈希表中移动到新的块内。
为两减少调整大小操作的开销，哈希值保存在名字树项内。我们下面介绍NameTree Node ,一个节点存储在块中，包含一个指针指向项，以及指向链上下一个节点的指针。调整大小操作只需要移动节点，而不需要改变项。
操作和算法
插入与删除操作
lookup/insertion(NameTree::lookup)操作通过给定的名字查找或插入一个项。维拉维持树结构,在必要式插入祖先项，当FIB，PIT，StretagyChioceTable,和Measurements table执行插入的时候调用该操作。
条件删除操作（NameTree::eraseEntryIfEmpty）用于删除那些没有FIB/PIT/StretagyChioce/Measurements，且没有子节点的项，该删除项的祖先节点若满足相同的要求也被删除，当FIB，PIT，StretagyChioceTable,和Measurements table执行删除的时候调用该操作。
匹配算法
精确匹配算法（NameTree::findExactMatch）用于查找特定名字的项，若没有该项就返回null。
最长前缀匹配（NameTree::findLongestPrefixMatch）通过EntrySelector操作来过滤，以查找特定名字的最长前缀匹配项，EntrySelector是一个predicate,用于判断是否一个项可以被接受。该算法由FIB最长前缀匹配算法调用，此时predicate只有当他包含一个FIB项的时候接受。由算法选测在寻找有效算法时调用，此时predicate只有当他包含算法选择项时接受。
全部匹配算法（NameTree::findAllMatches）通过EntrySelector操作来过滤，枚举所有以所给名字为前缀的项。算法实现：首先执行最长前缀匹配额，去除名字最后的部分，直到到达根项。该操作由PIT数据匹配算法调用。
枚举操作
全部枚举算法（NameTree::fullEnumerate）通过EntrySelector操作来过滤，枚举所有项，由FIB枚举和算法选择枚举调用。
部分枚举算法（NameTree::partiallEnumerate）通过EntrySubTreeSelector操作来过滤，枚举在特定名字前缀下的所有项,
Shortcuts
使用名字树的好处是在包的转发中减少产找索引，为此，一种方法是使转发管道明确执行名字树查询，但这种方法并不是最好的，为实现减少索引次数的同时从转发管道中隐藏名字树，我们在两个表之间添加shortcuts，每一个FIB，PIT，StretagyChioceTable,和Measurements table项包含指向对应名字树项的指针，例如，给定一个PIT项，通过指针可以检索对应的名字树项，之后检索或附加一个Measurement项，或最长前缀匹配FIB项。
通过这种方法名字树项仍然暴露在转发中，为将线该页隐藏起来我们介绍新的表覆盖算法（overload to table algorithms）,采用x相关表的项来取代名字，包括：
- Fib::findLongestPrefixMatch，用PIT项或测量项取代名字
- StrategyChoice::findEffectiveStrategy 用PIT项或测量项取代名字
- Measurements::get，同FIB项hugoPIT项取代名字
为支持覆盖，名字树提供NameTree::get方法，它可以用来返回与FIB，PIT，StretagyChioceTable,和Measurements table关联的名字树项。