memory - 用于存储非重叠间隔的数据结构 + 算法

Question

我想知道你们中是否有人知道存储非重叠间隔的节省空间的方法。我的最终目标是使用它来分配虚拟地址空间（我正在编写一个有趣的操作系统）并且想知道是否可以以比 O(n) 空间复杂度和 O(n) 搜索更好的方式存储空闲空间区域复杂。

概率数据结构可以工作，因为我总是可以遍历页表以找出地址空间是否可用。

谢谢。

Answer 1

R-Trees可用于此。它们也用于 2D（可能还有 N 维）结构，但也可以管理您需要的 1D 项目。

Answer 2

看看R 树。