哈希树和cursor代码索引同步逻辑以及tab逻辑的推理学习
一些通用工程技术学习
背景
这篇文章的内容其实是25年下半年学习的，但是有点懒，导致一直没有写一篇文章做记录，前段时间看到了cursor官方发布的文章 安全地为大型代码库建立索引， 回想起来之前学习过相关的内容，这里基于个人的拙见做一些备份记录.
两篇不错的文章可以学习 哈希树 Real-world engineering challenges: building Cursor
哈希树 (Merkle Tree)
哈希是什么这里就不再解释了，而哈希树说白了就是 树状结构+哈希 构成的树. 在标准的哈希树中，只有叶子节点包包含了数据以及自己的哈希值，父节点不干活，内容完全由子节点决定，也就是说父节点只包含了一个哈希值 (左子节点哈希 + 右子节点哈希).
聪明的你可能会有疑问，既然标准哈希树中的父节点压根不存储数据，只存储哈希值，那为什么还要费劲老大劲构造一个树？ 直接用哈希列表，这样不是更加清晰吗？
这也是我在学习到这个结构时产生的疑问。此时仔细想想，哈希代表了唯一值，如果使用哈希列表，只有一个根哈希，如果我们检测到了根哈希不同，如何去找哪一个(些)叶子结点的哈希值不同？ 此时只能遍历所有叶子节点了，很显然此时是O(n)的时间复杂度，但如果是树形结构，很显然此时是二分的逻辑，时间复杂度是O(logN). 所以可以得出结论，这是验证效率的问题^^
你觉得你是哈希搜索树吗？
搜索树顾名思义，就是一种搜索特化的属性结构，在和哈希没关系的树形结构中，搜索树有严格的排序规则，并且在中序遍历中也一定是升序的. 哈希搜索树定义更复杂一点：它既是一棵搜索树（可以通过 Key 进行 O(logN)查找），又是一棵校验树（可以快速比对两棵树的某个子节点及其下的所有数据是否一致）。
按照上一节的逻辑，我们可以通过标准哈希树来进行搜索操作，这种结构提供了极致的校验效率. 聪明的你可能又发现了这种结构似乎只能用于验证哈希值是否相同. 如果叶子节点插入的顺序不同，那么它的根哈希还相同吗？ 我个人认为是不相同的，并且在IDE和云端同步时多半会产生这种情况.
这里和git不同，我认为git本质上存储的是一个静态的状态(一个个分支、commit...etc)，所以标准哈希树应该可以用来表示git的存储结构。但我们的代码仓库是一个会频繁变化的数据集合，标准哈希树无法解决这个顺序问题.
回想一下聪明的你提出的第一个问题，你说'标准哈希树中的父节点压根不存储数据，要他干嘛用'. 一个核心的差异点就在这里，我们可以让哈希树的父节点也存储key，代码仓库的结构是一个天然的目录，我们可以存储一个基于代码目录结构的哈希树.
根据我的理解，这虽然不是学术意义上的哈希搜索树，但是功能上是类似的：哈希搜索树的一个核心特点就是确定性，无论按照什么顺序插入key，生成的树结构都是一样的。这不就是我们的代码目录嘛，一切都说得通了.
代码索引
我们已经明确了cursor存储代码的数据结构：基于代码目录结构的哈希树. 那么cursor针对这个结构做了什么事呢?
首先可以想到的是，cursor的客户端和服务端都存储了一份哈希树. 我们此时假设一个场景，我们修改了index.html中的一行代码, 那么和index.html这个文件向上的目录文件的哈希值会变动. 
剪枝说明
在进行客户端哈希树、服务端哈希树diff时，可以在O(logN)的时间量级中找到不同的子树进行同步. 这里需要注意，服务端在diff阶段是不会存储源代码的，否则会产生大量的存储空间，所以只存储基于目录结构的哈希树. 如果不使用哈希树来存储，那么同步的时间量级就是O(N)级，因为需要遍历所有代码来找到不同的位置，再进行同步. 费这么大劲但是没有存储源代码，只存储了哈希树，目的就是方便服务端快速存储和diff.
tab逻辑推测
我们在通过agent对话或者tab补全时，代码的计算一定是在服务端完成的。通过我们刚才的说明，服务端并没有存储完整的源代码，而是存储了一套基于代码目录的哈希树结构. 这给tab补全提供了基石：tab需要极快的速度来感知代码上下文的变化，而且不仅仅是正在修改的代码，还包含了一些关联信息。所以哈希树保证了cursor的代码库知识保持新鲜.
现在还剩下最后一个问题，cursor服务端在什么时候获取到了源代码信息? 我认为答案是哈希树定位到差异之后: 首先客户端计算出index.html的哈希以及路径上的哈希变化，客户端和服务端哈希树sync，发现index.html的哈希不同，此时将切块的代码发送给服务端进行计算. 模型计算完成后返回推荐结果给客户端.
这里引用一下pragmaticengineer的图片
一旦服务端拿到了最新的代码，由于只是很小的一部分（增量），它可以在毫秒级完成两件事：
- 同步：保证服务端持有的代码状态和客户端一致。
- 更新向量索引：立即对这段新代码计算embedding向量，更新向量数据库。 这就是为什么当你写完定义，立刻跳转到另一个文件按tab时，cursor依然能补全出来的核心原因：哈希树保证了同步的速度，而增量同步保证了数据的鲜活.
同时可以管中窥豹的是，agent等模式也是用了相近的方式，只是多了一步，用户可以自行选择相关的代码上传到服务器，剩下的步骤其实是相同的。 文章中省略了一部分客户端、服务端通信时的加密解密逻辑