Datastructure + Algorithm for storing non-overlapping intervals

Question

Hi, 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.

Answer 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.

Answer 2

Have a look at R Trees.