在本系列的第一部分中，我们对车队架构进行了概述。在第二部分中，我们将介绍在编辑器的封面下使用的算法和数据结构。
这里有一行带语法突出显示的文本，还有一个小部件提供关于特定变量用法的信息。现在人们可以找到多种方式来显示这些信息，但编辑的问题是它们不是只读的。除了数据的可视化，它们还可以更新。一个简单的操作，比如更改函数名，可能会影响很多事情，比如语法高亮显示、用法，当然还有其他任何功能，比如静态分析或动态编译。
为了能够提供良好的体验，我们需要确保编辑文本和随后的可视化尽可能无缝。为了实现这一点，我们必须以高效的方式存储和操作数据。然而，这不仅仅是存储数据的一种方式。事实上，上面的图像以多种方式存储数据，使用不同的数据结构，这些数据结构组合在一起形成我们所说的编辑器。换句话说，把编辑器想象成数据结构的聚合器！
对于那些熟悉处理大量文本的人来说，您可能已经知道使用字符串（即字符数组）来存储它们不是很有效。通常，对数组的任何操作都意味着必须创建一个更大或更小的新数组，并将内容从旧数组复制到新数组。这几乎没有效率。
更好、更标准的方法是使用绳索结构。这种抽象数据类型背后的思想是将字符串存储在树的叶节点中。
每个叶节点包含一个字符串及其长度（称为权重），每个中间节点还包含一个权重，该权重是其左子树中所有叶的总和。
从上面的例子来看，如果我们以包含字符fun的节点为例，节点的计数是3，因为字符串的长度是3。向上移动到父节点时，计数也为3，因为其左侧所有节点的权重之和为3。它的父代依次计数为19，因为它左边的叶子之和是3和16。
搜索、追加、删除、拆分字符串等常见操作的时间复杂度为O（logn），其中N是字符串的长度。操作从遍历一棵树开始，并且给定节点的信息，这会使操作更快。例如，如果我们想在位置i=30处找到一个字符，我们从节点开始，如果30小于节点的权重（字符数），我们向左，从i中减去权重值（见下面的注释）。如果另一方面i更高，我们向右。当我们向下移动，i的值减小时，一旦我们到达一个叶节点，叶节点所在字符串i位置的字符就是我们要寻找的。
注意：根据使用的度量，减法可能不是必需的操作。重要的是，当我们沿着树向下移动时，我们将度量累积到该点，并将其与我们正在扫描的键进行比较。
在Fleet的绳索结构中插入或删除节点时，我们使用自平衡B树。我们从读取64个字符的块开始，一旦达到32个块，我们就创建一个节点，并开始为第二个节点收集块。每个节点有两个数字——除了权重之外，我们还存储行数（两者的组合就是我们所说的度量）。
通过存储行计数，我们可以更快地导航到特定偏移。舰队中树的另一个特点是，我们的目标是保持它们宽而不是深。
正如我们之前看到的，代码片段可能不仅包含实际文本，还包含其他元素，比如用法。
我们称这些小部件为行间小部件，比如Find Usages或Run小部件、postline（例如出现在代码行之后的调试信息）或inlay（例如变量和lambda上的类型提示）。
小部件本身只是一个标记元素，保存它的数据结构是区间树的一种变体，在某种程度上也是一种绳结构。在区间树中，节点拥有一个范围，权重对应于子树中范围的最大值。
在Fleet中，每个节点都包含子节点的相对起点和终点。叶子依次包含一个实际的小部件。当运行查询以查看是否需要基于某个特定坐标显示特定的小部件时，我们遍历树，直到找到该范围与我们正在查询的范围的交点。
一个重要的方面是，叶子还包含小部件ID。这意味着除了查询与特定范围相交的内容外，对于任何小部件，我们还可以查询以确定其实际位置。
标准间隔树的一个变化是，在舰队中，我们允许节点重叠。这可能会降低搜索的效率，但通过允许这一点，我们可以创建平衡树，并在键入时对其进行更新。
除了小部件，Fleet中的间隔树还用于跟踪插入符号、突出显示文本，以及文本中我们称之为锚的粘性位置。
在处理源代码时，无论是编译器还是编辑器，通常都会使用抽象语法树（Abstract Syntax Tree，AST）。其工作方式是解析器分析源代码并创建一系列标记。然后，这些令牌用于构建AST。
每个标记都用方括号表示（注意空格也是标记）。然后使用这些令牌构建相应的AST
AST随后用于各种操作，如语法高亮显示、静态分析等。它是任何IDE的重要组成部分。
顺便说一句，如果你有兴趣了解一些代码是如何被翻译成AST的，可以看看这个很酷的在线AST浏览器（它支持多种语言）
当我们在编辑器中键入时，文本会发生变化，这意味着标记会发生变化，这反过来需要构建一个新的AST，以便能够提供上述功能。
在Fleet中，为了避免直接更新AST，我们使用rope结构将令牌存储在叶子中（实际上只存储长度）。举个例子，上面的令牌列表可以用下面的树表示
当用户键入某个内容（例如空格字符）时，树将被更新（最左边的叶子中添加了1的长度，导致该路径上的计数增加）
特定的叶子会添加新的标记长度，这反过来会导致更新树的某些节点，以调整权重。然后，解析器会收到一个通知，强制它更新并重新分析AST。因此，在一小部分时间内，AST可能并不完全正确，但在编辑方面，用户体验要好得多，因为几乎不需要更新。
下面的图片是编辑器的另一个例子，但这一次添加了一些额外的元素，即“实际用法”小部件，它被扩展以显示用法、行的软包装以及其他内容，例如滚动条中的彩色垂直线。
为了呈现上述内容，对于特定的Y坐标，我们不仅需要知道显示哪条线，还需要考虑所有小部件和软包装线。
有趣的事实：usages小部件中呈现的编辑器使用了我们在本文中探讨的相同的底层数据结构。对于同一文件中的用法，使用相同的绳索构建和渲染此覆盖编辑器。
小部件和软包装信息也存储为绳索结构。而在树的叶子可以容纳字符串和它的长度之前，在本例中，我们使用叶子来容纳我们所说的软线对象。这些是文本块和高度，被视为视觉线条。在这种情况下，节点的权重（我们称之为度量）是软线的高度和长度。存储高度是为了能够支持视口查询。此高度受其内部的中间线影响。此外，启用软包装时，软线不会与实际线一一对应，但可以跨越多条线。
值得一提的是，在舰队中，我们信奉不变性。使用纯函数和不可变对象有很多好处。纯函数不仅让我们能够更好地解释代码，还让我们知道调用函数不会导致系统的其他部分在我们不知情的情况下发生变化（即产生副作用）。就数据而言，知道一个对象是不可变的意味着它是线程安全的，因此在尝试任何更新时都不会有竞争条件。对于多线程环境，这提供了巨大的好处。
这种不变性的想法对于使用绳索结构的操作也是至关重要的。之前我们讨论了如何更新树的节点和叶子。这些都是以不变的方式完成的——树上的任何操作都会生成树的新副本，该副本与旧副本共享结构，但从根到需要更改的单个节点除外。事实上，这些树一般都很宽，并不深，这意味着路径很短。如果操作导致任何未引用的节点，这些节点将被垃圾收集。
这与我们在IntelliJ平台上使用读写锁定机制来执行更改的做法截然不同。
正如我们在关于如何构建舰队的第二部分中所看到的，像编辑器这样简单的东西，我们可以在其中键入和读取代码，结果是一个复杂的多个不同数据结构的底层聚合，其中许多是绳索。如果你有兴趣了解更多关于绳索的知识，一定要看看绳索科学系列，它对我们在舰队上所做的工作产生了重大影响。