.tree 文件格式

.tree 文件格式允许您有效地存储和查询树结构。它不是人类可读的格式，因为其数据以字节存储，并由您的程序解释为自身数据。

术语表

标题

标题指定数据在文件中的存储方式。正确配置文件标题对于优化性能（和文件大小）非常重要。

标识

[0; 8)

文件以以下8字节开头： 4e 45 4b 4f 54 52 45 45。这必须是文件的第一个8个字节。

格式版本

[8; 10)

接下来的两个字节是表示格式的版本，以二进制形式表示。

版本

功能

[10; 12)

接下来的两个字节表示在树中启用的功能。一个 1 表示该功能已启用。可以忽略不表示功能的位。额外的位表示如果启用功能，则将添加到每个项目中的位数。

[!重要] 特性按切换它们的位的顺序排列很重要，稍后在向每个树项目添加数据时。

子项

[12; -)

此标题指定树中子项的数量和大小。子项的顺序保持不变。

[4 bytes: Amount of sub-items]
(
    [4 bytes: Sub-item size]
    for subitem in 0..amount_of_subitems
)

子项数量

[12; 16)

每个树项包含的子项数量，以二进制表示。

子项大小

[16; -)

每个子项的大小（以位为单位），以二进制表示。每个项大小占用四个字节，且所有子项大小都不能缺失。

树

树可以存储任何可以用位表示的内容。每个程序都可以读取文件并解释为自己的数据。

以下是以以下方式扁平化存储树

     A        <- Level 0
   /   \
  B     C     <- Level 1
 / \   / \
D   E F   G   <- Level 2

被转换为

0 1  2
A BC DEFG

这样，树就被扁平化了。树需要每个项恰好两个分支。最后一层不会有任何分支。

树项

树中的每个项由一个或多个子项（在标题中定义）组成。每个子项在位上有固定长度（在标题中定义），并且必须精确遵循该大小。

功能

这些功能可以在标题中启用和禁用。有关更多信息，请检查上面的功能标题。

每个项都有自己的标题，由上面的功能指定。标题在顶部的顺序保持不变。即使对于特定项不需要，标题位也必须存在。

即使对于特定项没有意义，标题也必须存在。例如，根项不能被扁平化，但它们仍然会分配一个用于扁平化的位，该位将被忽略。

以下图表表示了项的结构

(
    [n bit: Header]
    for n in item_header_sizes
)
(
    [n bits: Sub-item 1 content]
    for n in subitem_sizes
)

您不得添加对应未启用的功能的位。每个功能分配的位数可以在功能标题中检查。

禁用

禁用允许您禁用分支及其子分支。请注意，它们仍然占用与其他项相同数量的位，但在读取树时不会被考虑。启用此功能允许您存储不对称的树。例如

     A
   /   \
  B     C
 / \   / \
x   x F   G

在上面的例子中，B仍然有自己的项，但它们被禁用，因此处理树时会被忽略。这是为了保持树的结构的可预测性，以实现更有效的查询。

如何禁用项

当此功能启用时，所有项都必须有一个额外的1位前缀。该位启用（0）或禁用（1）项。如果项被禁用，则可以忽略该项的内容位。请注意，它们仍然必须存在。

子项

每个项的子项是该特定项中存储的数据的一部分。它们没有单独的标题，并且按顺序放置。

子项按顺序放置，顺序与文件标题中的定义顺序相同。

其他主题

字节对齐

如果文件未对齐（位的长度不是8的倍数），则可以使用0填充文件。

文件结构图

以下“图表”说明了完整的.tree文件的外观

{ Headers:
    [8 bytes: File identifier]
    [2 bytes: Format version]
    [2 bytes: Features]
    [4 bytes: Amount of items]
    (
        [4 bytes: Item x size] 
        for x in amount_of_items
    )
}
{ Tree:
    (
        [n bits: Item header]
        for n in item_header_sizes
    )
    (
        [n bits: Sub-item content]
        for n in subitem_sizes
    )
}
[? bits: Padding]