Kie*_*one 12 c# b-tree data-structures
我正在研究为我的应用程序整合自定义存储方案的可能性.我认为值得重新发明轮子的努力是值得的,因为性能和存储效率都是主要目标,其上的数据和操作比RDBMS提供的更简单(没有更新,没有删除,预定义的查询集) ).
我使用网络资源的只是极少数,我发现关于B树和B + -树-维基百科,http://www.bluerwhite.org/btree/,http://slady.net/java/bt何种交往,http://www.brpreiss.com/books/opus6/html/page342.html(最后一个是最有价值的).
我试图解决的第一个问题是如何处理重复键 - 这个树将充当DB索引,例如,不会只有'color = red'的'thing',所以查找'这棵树中的红色应该产生很多结果.
到目前为止,我提出了两种解决方案.第一种是在树中为这些中的每一个简单地具有多个条目.但是,当树中有100,000或1,000,000个"红色"东西时......对树结构来说是非常有效的吗？第二个是每个键只有一个条目,但与每个键关联的"有效负载"指向不同的数据块,这是一个指向"红色"项目的所有实例的链接列表.
有共同/更好的选择吗？
我想检查一下我正在做的假设.假设您有一个B + -Tree,高度为2 - 级别2的外部(叶子)节点保存"实际数据".然后插入需要分割叶节点 - 叶节点不再保存'实际数据'.我是否正确地认为在实现方面,因为数据可能具有相当大的尺寸,您可以将一种"指针"存储为"实际数据" - 因此,如果叶节点成为分支节点,那么指针(相反大小)更新为指向新子树？
我的意思是,内部和外部节点,它们应该是相同的大小,因为外部节点可能成为内部节点,并且改组数据不是一个好主意？
(添加了C#标签,因为我在C#中从头开始实现它.)
小智 6
Kieren,我相信你现在已经发现B +树通过向上分裂而增长,因此叶子节点总是一个叶子节点,内部节点总是内部节点.最终,您必须拆分根节点,将其转换为两个内部,然后定义新根.因此,要回答问题的第二部分,请不要更改节点类型.
关于问题的第一部分,当您从数据库中删除数据记录时,您需要找到指向该特定记录的所有密钥,然后将其删除.如果您必须查看长线性列表来执行此操作,则删除速度会很慢.我假设你在一个节点内使用二进制搜索,以便快速找到正确的节点元素(键+指针),所以如果你使"节点搜索"机制包括要求特定键+指针组合的能力,您可以快速找到要删除的正确密钥元素.换句话说,使数据记录指针成为搜索的一部分(仅在搜索特定数据记录的密钥时).这意味着重复键将以"数据指针"顺序存储在节点中,因此只要重复键的排序不重要,此机制就可以工作.
试图回答我自己的问题..我也欢迎其他答案.
如果可能存在相同密钥的重复条目,则树将存储对具有给定密钥的项目的列表(存储器)或链接列表(磁盘)的引用.
在内存中,我的节点有一个object引用,在内部/分支节点的情况下可以指向另一个节点(本身是另一个有效的B + Tree),或者在外部/叶子节点的情况下直接指向数据.在磁盘上,这将以非常类似的方式工作:每个"链接槽"的64位值,因为我选择命名它们 - 如果指向子节点,则是文件中的偏移量,或者是块编号如果直接指向数据(或在问题的第一部分中提到的情况下链接列表的头部).