Click here to Skip to main content
15,889,281 members
Please Sign up or sign in to vote.
0.00/5 (No votes)
See more:
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.!
Posted

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.
 
Share this answer
 
v3
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
 
Share this answer
 
"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.
 
Share this answer
 
hi,everybody
everybody can help me ,solution how can i store data of file xml into B-tree. because my teacher require us,read file large xml and store them into B-tree, exact we have to do a english-viet dictionary. but i don't know how can i do. i expect everybody can help me.thanks.
 
Share this answer
 

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900