b树记录索引器实现

问题描述

你好，
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.!

推荐答案

这篇关于b树记录索引器实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！