简单的。制作偏移量的二叉树。
任何偏移量的值都是通过从叶子到根遍历树来计算的,只要节点是右子节点,就添加偏移量。
然后,如果您在文件的早期添加文本,您只需要更新节点的偏移量,这些节点是更改的偏移量的父节点。也就是说,您在第一个偏移量之前添加了文本,您添加了添加到根节点的字符数。现在您的一半偏移量已得到纠正。现在遍历左孩子并再次添加偏移量。现在 3/4 的偏移量已更新。继续遍历左孩子添加偏移量,直到所有偏移量都被更新。
@OP:
假设您有一个包含 8 个字符的文本缓冲区,以及奇数字节的 4 个偏移量:
the tree: 5
/ \
3 2
/ \ / \
1 0 0 0
sum of right
children (indices) 1 3 5 7
现在假设您在偏移量 4 处插入了 2 个字节。缓冲区是:
01234567
现在它的
0123xx4567
因此,您只修改支配数组中已更改部分的节点。在这种情况下,只需要修改根节点。
the tree: 7
/ \
3 2
/ \ / \
1 0 0 0
sum of right
children (indices) 1 3 7 9
求和规则是从叶到根我对自己求和,如果我是父母的正确孩子,我的父母的价值。
要查找我当前位置是否有索引,我从根开始并询问此偏移量是否大于我的位置。如果是,我会向左移动并且什么都不添加。如果没有,我会向右遍历并将值添加到我的索引中。如果在遍历结束时我的值等于我的索引,那么是的,有一个注释。您可以使用最小和最大索引进行类似的遍历,以找到支配范围内所有索引的节点,找到我正在显示的文本的所有索引。
哦..这只是一个玩具示例。实际上,您需要定期重新平衡树,否则如果您继续在文件的一部分中添加新索引,您将得到一棵失去平衡的树,最坏情况下的性能将不再是 O( log2 n) 但将是 O(n)。为了保持树的平衡,您需要实现一个平衡的二叉树,如“红/黑树”。这将保证 O(log2 n) 性能,其中 N 是元数据的数量。