b树记录索引器实现 [英] b-tree record indexer implementation
问题描述
你好，
iv'e在网络上遇到了几个b + tree示例
一件事仍然不清楚
据我了解:
1)让iv'e得到一棵3阶的树(order = 3)
这意味着每个节点都包含:
(阶-1)键(2)和(阶)指针(3)，巫婆可以指向任一叶节点
或内部节点
2)只有叶节点包含对记录的引用
并且内部节点包含对其他节点的引用.
我的结论(和问题):叶节点最多包含2个指向记录的指针(引用)，
当我开始实现时，我以为叶子节点将引用
的订单号
记录(3)
现在与思想让我们添加三个记录相矛盾
`tree.Add(5，new Record());
tree.Add(8，new Record());
tree.Add(10，new Record());`
我有一个女巫的照片显示了为什么我得出这个结论
它显示了以下情况
hello ,
iv''e come across several b+tree examples on the web
and one thing still isn''t clear
to my understanding :
1)lets say iv''e got a tree with the order of 3 ( order = 3 )
that means each node contains :
( order -1 ) keys (2) and (order) pointers (3) , witch can point at either leaf nodes
or internal nodes
2) only the leaf nodes contain references to records
and the internal nodes contain references to other nodes .
my conclusion (AND QUESTION) : leaf nodes contain a maximum of 2 pointers(references) to records ,
when i started implementing i thought that the leaf nodes will reference order number of
records (3)
now to contradict that thought lets add three records
`tree.Add( 5 , new Record()) ;
tree.Add( 8 , new Record()) ;
tree.Add( 10 , new Record()) ;`
i had a picture witch showed why i came to this conclusion
it shows the following scenario
Root
|
N1 | 8 | NULL |
/ \ n3 \
n2 |5 |NULL| |8 | 10 | =
/ \ \ / \ \
(Record) = = (Record) (Record) =
('' = '' means points to NULL )
N1 -> root node containing one key (8) and 2 Pointers To Leaf Nodes N2 , N3 ;
N2 -> leaf node containing one key (5) and one pointer to a its record;
N3 -> leaf node containing tow keys (8,10) and 2 pointers tow each of their records.
因此，在任何情况下，叶节点只能引用尽可能多的记录，而该记录可以包含键
(顺序-1)，在这种情况下为2条记录.
请阐明这个话题，我解释了我的理解，如果有人会承认或反对我的理解，我会感激的.
so in any scenario a leaf node could reference only as many records as it can hold keys
(order -1 ) , 2 records in this case .
please shed some light on this topic , iv''e explained what i understood i''d appreciate it if some one would acknowledge or contradict my understandings . thanks in advance.!
推荐答案
每个叶节点都有三个指针，即使它只存储两个键，也可以指向三个记录.
在某些祖先节点中找到了丢失的键(除了第一个记录).
看一下 http://en.wikipedia.org/wiki/B-tree [ ^ ]:叶子中有11条记录，共有10个键在叶子或内部节点中.叶子比记录少一键.
Every leaf node has three pointers and can point to three records, even though it only stores two keys.
The missing key is found in some ancestor node (except for the very first record).
Look at the figure of http://en.wikipedia.org/wiki/B-tree[^]: there are 11 records in the leaves and a total of 10 keys either in leaves or internal nodes. The leaves have one key less than records.
是的，相似的图纸促使我提出这个问题，
我实现的是B +树，而绘图是B树，我认为他们的算法
可能会有所不同.
B +树还可以用于记录的顺序排序遍历
叶子确实感染保持指向顺序1的记录的指针，而指向顺序1的指针指向同级节点.
B + tree Wikipedia
yes, similar drawings are what led me to ask that question ,
what i implemented is a B+tree that drawing is of a B-tree i think their algorithms
might be a bit different .
the B+tree could also be used for sequential sorted traversal of the records
the leafs do infect hold pointers to order - 1 records and the pointer at place order - 1 points to the sibling node .
B+tree Wikipedia
"，请对此主题有所了解. .."
在下面的链接上有很多指示灯:
http://www.sanmayce.com/Downloads/Leprechaun_%5Bquadrupleton%5D_r13_7pluses_ELFs_EXEs.zip ^ ]
在普通C中实现了3阶 B树，没有删除操作.谈到速度性能: 它尖叫 .
"please shed some light on this topic ..."
Hi,
at link below there is a lot of light:
http://www.sanmayce.com/Downloads/Leprechaun_%5Bquadrupleton%5D_r13_7pluses_ELFs_EXEs.zip[^]
There B-tree of order 3 is implemented in plain C, without delete operation. Talking of speed performance: it screams.
这篇关于b树记录索引器实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
