我正在编写一个Roslyn驱动的C#编辑器。Roslyn 语法验证要求我在每次按下击键时提交 C# 源文件的整个编辑缓冲区以供分析。缓冲区必须是快照，因此我无法包装实际的实时编辑缓冲区。
目前的算法，等待"永不优化"规则过期：每次击键分配一个新的char[]数组，并将编辑器文本序列化到数组中，不注意实际操作是什么。
令人惊讶的是，性能并不糟糕。但我担心在大型项目中用大量拨款来破坏垃圾收集器。想象一下，在编辑大型 C# 文件时，每次击键分配一个 2MB 的缓冲区。从长远来看，这不可能是好事。
我从内部消息来源知道Visual Studio使用某种"二叉树"数据结构来提交增量更新。但是Visual Studio的这一部分的源代码不可用。
我想象一种算法大致如下：将整个编辑缓冲区拆分为易于管理的小块。每次按下某个键时，对文档的更改都会插入、删除或替换一个或多个字符。因此，与其分配新的缓冲区，不如使用在更改中拆分和修补的策略;然后用 A 接口包装整个数据结构，该接口将片段呈现为连续的顺序块。与其分配大量的大型对象结构，这将迫使Gen2 CG，不如分配小块来影响补丁。
大概是一些合并策略，也许在优先级最低的线程上。
我可以临时去做，但我忍不住想，一定有一些正式的算法来处理这个问题。
任何人？(我想是一对交换的缓冲区。但是...
我知道有三种主要的数据结构用于文本编辑器缓冲区，间隙缓冲区，块表和绳索数据结构。您描述的树结构可以应用于绳索数据结构或计件表，但对于计件表不是必需的。
谷歌员工在 https://xi-editor.io/xi-editor/docs/rope_science_00.html 上提供了许多关于绳索数据结构的文章，这些文章非常好并且独立于编程语言(xi编辑器本身是用rust编写的(。
片段表 (https://darrenburns.net/posts/piece-table/( 可以作为树形数据结构实现，但也可以只是文件每一行的字符串数组，事实上，这就是 VS Code 在 2018 年左右所做的。
Gap 缓冲区 (https://en.wikipedia.org/wiki/Gap_buffer( 可能是最简单的方法，对于许多用例来说足够快，但由于潜在的大内存副本，在大型文本文件上使用时会受到影响。
我不熟悉 Roslyn API，但跟踪上述结构之一中的编辑，然后在后台线程上将文本缓冲区提交给 Roslyn 时构建完整版本至少听起来很合理。
相关算法：张开树，红黑树。
以下文章介绍了 Visual Studio 使用的实现
https://code.visualstudio.com/blogs/2018/03/23/text-buffer-reimplementation
一棵红黑树，其中包含可以拆分为碎片的缓冲区，但需要注意的是，它们的片段缓冲区最终会碎裂，因为它们不会尝试合并。
实现是....非常困难，我对正确性感到严重关切。:-)将已经非常困难的红黑树算法修改为基于文本位置是......真的真的很难。
我目前想知道 O(n( 插入的复杂性是否如此可怕，因为我将立即转身并将结果提供给乐观地为 O(n log(n(( 进行处理的 C# 解析器。