git - 代表 Git 存储库的数学结构是什么

Question

我正在学习 Git，如果我能对代表 Git 存储库的数学结构进行描述，那就太好了。例如：它是一个有向无环图；它的节点代表提交；它的节点有标签（每个节点最多一个标签，没有标签使用两次）代表分支等。（我知道这个描述不正确，我只是想解释我在找什么。）

Answer 1

除了 Nevik Rehnel 评论中的链接（根据请求在此处复制： eagain.net/articles/git-for-computer-scientists和gitolite.com/gcs），以及提交图形成 Merkle Tree 的观点，我我会添加一些注释。

• 对象存储中有四种对象类型：commit、tree、annotated-tag 和 blob（文件）。
• 一个提交对象只包含一个树引用（当然可以指向更多树）、一个可能为空的父 SHA-1 哈希列表（必须都是更多提交）、一个作者（姓名、电子邮件和时间戳） ，提交者（与作者相同的形式）和提交文本。
• 树对象包含重复 0 次或多次的（模式、子对象、文件名）列表。如果子对象是另一棵树，则文件名代表一个目录。如果它是一个 blob，它代表一个文件。该模式看起来像 POSIX 文件模式，如果是120000（符号链接的文件模式），则文件的“内容”实际上是符号链接目标。某些模式值（ab）用于子模块，但我忘记了。不存储 R 和 W 模式位，仅存储 X 位（即使存储库配置说忽略它们，它们也会被忽略）。
• annotated-tag 对象包含一个对象引用、一个标记器（名称、电子邮件和时间戳）和标记文本。引用的对象通常是一个提交，但标签对象可以指向任何对象（甚至是另一个标签对象）。
• 标签（分支和标签以及引用日志引用等）位于对象存储之外。对于带注释的标签，外面有一个标签，指向对象存储内的带注释的标签对象。对于轻量级标签，外部标签指向提交。
• 没有限制只有一个根提交。任何没有父母的提交都是根。
• Git 几乎从不创建一个空树（这将代表一个空目录），除了两种情况：每个 repo 中始终有一个空树，如果您进行初始空提交（使用git commit --allow-empty），它会使用该空树。（由于空树没有子对象，它的 SHA-1 哈希值是一个常数。）
• “DAG”描述通常用于通过关闭提交父哈希形成的树。然而，一个树对象通常不应该在它的任何子树中包含它自己，如果你设法创建一个循环树结构，你将无法检查它（因为它无限递归）。假设您不能创建具有相同校验和的两棵不同的树（如果您可以破坏 git），您将找不到包含树 T2 的树 T1，而树 T2 包含另一棵其校验和为 T1 的树。因此，这些树也隐含地是一个 DAG，并且附加到提交 DAG，它们形成了一个更大的 DAG。:-)
• 对象存储中未引用的对象将被git gc. 空树似乎对收集免疫。refs/andlogs/目录和文件中的任何内容packed-refs（在.git，或用于裸存储库或何时$GIT_DIR设置，其他任何地方）都充当参考，特殊名称（HEAD，ORIG_HEAD等）也是如此；我不确定其他随机文件（如果在有效 SHA-1 中创建.git并包含有效 SHA-1）是否可以作为参考。
• 该索引有一些我从未研究过的格式。它包含对对象存储中对象的引用。当您git add创建文件时，git 将文件放入对象存储中并将（非文本）SHA-1 哈希放入索引文件中。这些是防止垃圾收集的有效引用。

Answer 2

我认为最相关的答案需要包括 Git 修订树最重要的特征：加密签名（每个修订都包括父修订的哈希和提交细节）。

这被称为 Merkle 树：http ://en.wikipedia.org/wiki/Merkle_tree

---

查看一些背景的早期答案：（Git：如何处理提交以便文件的版本完整存在（不仅仅是差异））

背景

存储增量由 RCS、CVS、Subversion 和其他（SourceSafe？）普及。主要是因为该模型使传输变更集变得容易，因为它们已经是增量形式。现代 VCS-es（主要是分布式的）已经从这一点演变而来，并将重点放在数据完整性上。

数据的完整性

由于对象数据库的设计，git 非常健壮，可以检测快照或整个 repo 中任何位置的任何损坏的数据。有关 Git 存储库的加密属性的更多详细信息，请参阅这篇文章：Linus talk - Git 与数据损坏？

在 techno babble 中：提交历史形成加密强大的默克尔树。当提示提交 (HEAD) 的 sha1 总和匹配时，它在数学上遵循

• 树内容
• 分支历史记录（包括所有签核和提交者/作者凭据）

是相同的。这是 git 的一个巨大的安全特性（以及其他共享此设计特性的 SCM）