我将编写一个与zodb一起使用的通用对象类.一旦它们被持久化到zodb对象图,这些对象就会将它们添加到btree索引中.
我以前从来没有真正使用过这个,但是有人会有这方面的资源和/或建议吗？
有了zodb处理对象引用和良好索引策略的能力,我最终可以获得两个数据库世界的最佳效果.
任何其他想法都非常欢迎,谢谢!
我一直在玩slady.net上非常酷的btree小程序.我无法理解特定的行为.看看这个起始状态:
alt text http://www.freeimagehosting.net/uploads/db2931c7da.jpg
通过插入以下序列得到该特定状态:10,15,30,16,70,1,9,27,45,50,55.
我的问题是当我在序列中插入下一个值时,[45,]节点会发生什么,65.
alt text http://www.freeimagehosting.net/uploads/3b70c1d302.jpg
[55,70]节点将被65分割,并且作为中间值,65将返回,然后分割[30,50]节点.我的问题是:为什么[45,]节点最终成为[30,]节点的子节点？它的父母最初有3个孩子,最左边和最右边成为新的单独节点.45是在这些值之间,似乎它最终也可以在[65,]节点下结束......为什么？
我正在读考试,然后来到B树上.维基百科将B树描述为树,其中节点具有至少d且最多2d的密钥,因此最多2d + 1叶.例如,如果d = 1,它将有最多2个键和3个子项,使其成为2-3树.然而,除非我弄错,否则这不允许例如2-3-4树.
然而,我们的材料将b树描述为树,其中每个节点至少具有t> = 2 t-1个密钥和至多2t-1个密钥.这意味着节点具有奇数个键和偶数个子节点.例如,t = 2将具有1到3个键,最多4个子项,使其成为2-3-4树.另一方面,这种符号不可能有2-3棵树.
除此之外,Knuth还有一个符号,其中d表示节点中的最大子节点数.这种表示法允许偶数和奇数的孩子,允许2-3棵树和2-3-4棵树.
我知道2-3棵树和2-3-4棵树都存在.
什么是真正的符号？有真正的符号吗？作为一个额外的问题; 什么是大小为h的树中的最大键数？
如果您将b +树作为索引，那么这似乎与有序链接列表非常相似。但是，有序链表似乎具有一些优点，例如，不必导航树结构，也不必在节点装满时重建节点，并且不必在无平衡时重建树。
谁能回答使用b树而不是有序列表的原因？
我对红黑树和2-3-4树都有基本的了解,以及它们如何保持高度平衡,以确保最坏情况下的操作是O(n logn).
但是,我无法理解维基百科的这篇文章
2-3-4树是红黑树的等轴测图,这意味着它们是等效的数据结构.换句话说,对于每2-3-4树,存在至少一个具有相同顺序的数据元素的红黑树.此外,2-3-4树上的插入和删除操作会导致节点扩展,拆分和合并,这相当于红黑树中的颜色翻转和旋转.
我不知道这些操作是如何相同的.维基百科上的引用是否准确？怎么能看到操作是等效的？
我有一组(x,y)64位整数的元组组成我的数据集.比方说,我有数万亿这些元组; 将数据集保存在地球上的任何机器上是不可行的.但是,将它们存储在磁盘上是非常合理的.
我有一个磁盘存储(B + -tree),允许在一个维度上快速,并发地查询数据.但是,我的一些查询依赖于这两个维度.
查询示例:
x大于或等于某个给定值的元组x尽可能小的元组,它y大于或等于某个给定值x尽可能小的元组,它y小于或等于某个给定值我发现的最好的赌注是Z阶曲线,但我似乎无法弄清楚如何根据我的二维数据集进行查询.
不可接受的解决方案包括对数据的顺序扫描,这可能太慢了.
由于MySQL BTREE在创建索引时默认使用,我可以使用某些实例HASH吗？例如,如果我的表只包含外键,它们只是INT UNSIGNED值.在这种情况下用HASH覆盖BTREE是一个很好的改进吗？
不确定是否重要,但我正在使用InnoDB.
我已经实现了一个简单的B树,它将longs映射到整数.现在我想使用以下方法估计它的内存使用情况(仅适用于32位JVM):
class BTreeEntry {
int entrySize;
long keys[];
int values[];
BTreeEntry children[];
boolean isLeaf;
...
/** @return used bytes */
long capacity() {
long cap = keys.length * (8 + 4) + 3 * 12 + 4 + 1;
if (!isLeaf) {
cap += children.length * 4;
for (int i = 0; i < children.length; i++) {
if (children[i] != null)
cap += children[i].capacity();
}
}
return cap;
}
}
/** @return memory usage in MB */
public …我想从给定大小的无序元素列表中构建B +树N.
我知道这样做的最佳界限是?(N / B * logM / B(N / B))块传输,这也是排序的最佳选择; 所以我不能简单地选择一个项目并单独在树中插入,因为它会给我O(N logB(N))块传输.
所以我认为构建树的最佳方法是首先对元素进行排序,因为无论如何都要对树进行排序.从那以后,我很茫然.
我想过这样的事情:
B-1父母中有路由键时,表示它已满.所以新的路由密钥将改为"祖父"(因此树增长一级),所有新的叶子将有一个新的父级N/B读取块 基本上,问题在于我没有考虑内部节点可以拥有的最小子节点数.因此,例如,一个节点最终只有一个子节点,这显然是错误的.
我到处寻找,但我找不到实际解释如何构建树的算法?(N / B * logM / B(N / B)).我找到的只是在列表中为每个项目简单插入树的算法,而没有利用B因子.
你能帮助我吗,也许能指出我正确的方向？
我一直在考虑在开源项目中实现Bε树索引.据我所知,PerconaFT键值存储使用它们作为分形指数的基础,他们声称他们使用了几项美国专利 - 第8,185,551号和第8,489,638号.我不是律师,所以我有一个问题是否意味着没有其他人可以在他们的软件产品中实际实现基于Bε树的索引？