byte_trie

• crate: https://crates.io/crates/byte_trie
• 文档: https://docs.rs/byte_trie

这是一个专为字节序列设计的压缩 trie 结构。在想要创建 git Oid 哈希的序列化 trie 时创建的，这些哈希是 20 字节长数组。通过玩一些奇怪的节点大小东西来（希望）优化边节点的大小，因为 git oids 获取唯一性非常快。

性能目标是能够插入并序列化 linux git 仓库中的每个提交（825k+ 提交），它确实做到了。

有待改进，但现在它工作正常。

特性

• 插入
• 以十六进制形式序列化（功能 serde）

待办事项

• 删除（以及重新压缩）
• 文档
• 测试

序列化示例

trie 以与存储节点相同的方式将字节序列化为十六进制字符串。在序列化时跳过压缩的空节点，因此不应该有被序列化为空字符串的键。以下是从 25k 个提交的序列化文件中选取的几个提交的 TypeScript 仓库的少量 json 片段。

{
  "00": {
    "01": {
      "1a52af387cabeaddb261ca426529f1cdbe5a": "Refactor root files addition/update for non inferred project",
      "b8cb37e1988a4809aff8e5c8f55dd0f98ee6": "Remove target-following code when erasing signatures"
    },
    "0206fd8fdb5118d14371b0f5f033c311653ca5": "Update servicesVersion",
    "0637156aba40b51f7410c53783d01e27a73b6d": "Merge pull request #10374 from Microsoft/readonly-array-type-argument-assignability",
    "0f121d348913ca13ba1354f21adaf10eabc3c4": "Improve conditional type constraint checking",
    "10a38660b1eb03c188c9c1758177b4501760b7": "Merge pull request #28343 from Microsoft/lib/update-nov-2018",
    "130f1a68011ae59fb61e2f70897d48ec100b47": "Handle when using -p and config file not found",
    "16fd72f749f25561a4d70ad36978d48b3505c2": "Add test",
    "1b7b5bbe872d83ccb38ddb38ec70f0a2f1327a": "Merge pull request #2 from Microsoft/master"
  }
}

许可证

在以下两者中选择一个获得许可

• Apache 许可证第 2 版 (LICENSE-APACHE 或 http://www.apache.org/licenses/LICENSE-2.0)
• MIT 许可证 (LICENSE-MIT 或 http://opensource.org/licenses/MIT)

任选其一。

贡献

除非你明确说明，否则，根据 Apache-2.0 许可证的定义，你故意提交的任何旨在包含在作品中的贡献，都应按照上述方式双重许可，而无需任何附加条款或条件。