我正在尝试做的最有效的树结构

Question

我想知道对于具有以下要求的集合,最通用的树结构是什么:

1. 该树将容纳0到2 ³² - 1项之间的任何地方.
2. 每个项目都是一个简单的结构,包含一个32位无符号整数(项目的唯一ID,将用作树值)和两个指针.
3. 项目将经常插入树中并从树中删除; 树中的某些项目将在程序的持续时间内保留在那里,而其他项目在删除之前只会在树中非常短暂.
4. 删除项目后,其唯一ID(该32位无符号整数)将被回收并重新用于新项目.

树结构需要支持有效的插入和删除,以及通过唯一ID快速查找.此外,找到第一个可用的未使用的唯一ID需要是快速操作.

什么样的树最适合这些要求？

编辑:这棵树将只在内存中保存; 在任何时候它都不会被持久化到磁盘上.我不需要担心碰到磁盘,磁盘缓存或任何类似的东西.这也是我不打算使用像SQLite这样的东西的原因.

Answer 1

根据您需要多快的速度,您可以将整个事物视为单个内存表mmap-ed到文件中.寻址是通过直接计算.您可以简单地链接空闲插槽,这样您就可以确切地知道下一个空闲插槽的确切位置.大多数访问最多有1或2个磁盘访问(取决于底层文件系统要求).在计算机上放置一块内存,你可能根本不会碰到磁盘.

我知道这听起来很蛮力,但你会惊讶于它的速度有多快.

更新响应: "我不是在寻找磁盘可持久解决方案"

好吧,如果你真的要在这个结构中有多达2 ^ 32个项目(时间有多大),那么你需要在机器上有足够的内存来容纳这只小狗,否则内核会开始交换进出的东西记忆的你.这仍然转化为击中磁盘.如果你让它交换,不要忘记检查交换区域的大小,你很可能不得不碰它.使用mmap(或类似的东西)有点像创建自己的私有交换区域,它可能对同一系统上运行的其他进程的影响较小.

我会注意到,一旦这个东西超过你的可用物理内存(无论你是使用交换空间还是mmap或B-tree或Black-Red或可扩展散列等),了解你的访问模式就变得至关重要.如果你在整个地方进行跳房子游戏,那么你将会大量击中磁盘.使用像B树(或几个类似结构中的任何一个)之类的结构的主要原因之一是树的顶层(包含索引)倾向于留在内存中(因为大多数分页算法使用LRU)和您只有在触摸叶子页时才会访问磁盘.

底线:它要么适合内存,要么不适合.如果没有,则您的10 ^ -9秒内存访问将变为10 ^ -3磁盘访问.比慢一百万倍. TANSTAAFL!