Datastructure + Algorithm for storing non-overlapping intervals

Datastructure + Algorithm for storing non-overlapping intervals

不再见 发布于 2021-11-27 字数 496 浏览 802 回复 2 原文

I was wondering if any of you guys knew of a space efficient way of storing non overlapping intervals. My end goal is to use this to allocate virtual address space (I am writing an operating system for fun) and wanted to know if one could store the regions of free space in better than O(n) space complexity and O(n) search complexity.

A probabilistic data structure could work because I can always walk the page table to find out if the address space is available.

Thanks.

如果你对这篇文章有疑问,欢迎到本站 社区 发帖提问或使用手Q扫描下方二维码加群参与讨论,获取更多帮助。

扫码加入群聊

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(2

小情绪 2022-06-07 2 楼

Have a look at R Trees.

暖伴 2022-06-07 1 楼

R-Trees can be used for this. They are also used for 2D (and probably N-dimensional) structures, but can also manage 1D items such as you require.