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.
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.!