btree or b+tree

Kenneth Sørensen · *nix forums beginner Joined: 03 Mar 2005 Posts: 6

Hey,

It seems like BDB by default does not coalesce the nodes in the B+-tree.

It does the same whether I have specified the DB_REVSPLITOFF flags on the
creation of the database or not.

The scenario i'm trying to run is the following.

1. open the database (with or without the DB_REVSPLITOFF flag -> same
observation as below)
2. fill in 50 entries (which is more than what can be inside a single
leafnode) -> observation: The tree splits into the a root-node and 2
leafnodes (one with 48 entries and one with 2 entries)
3. deleting the 40 first entries -> observation: the tree now still contains
tree nodes (leafnodes now have 8 and 2 entries)

After doing this i guess it should be expected that the 10 entries back
where coalesced into the root node? The behavior seams like the REVSPLIT is
always turned off. Is there an explanation for my observation?

Regards,
Kenneth

"Michael Cahill" <mjc@sleepycat.com> wrote in message
news:1112273035.741722.288450@z14g2000cwz.googlegroups.com...

Michael Cahill · *nix forums Guru Wannabe Joined: 26 May 2005 Posts: 219

Hi Claus,

Yes -- what you call coalescing is what Berkeley DB calls a reverse
split. You can turn it off with the DB_REVSPLITOFF flag:

http://www.sleepycat.com/docs/api_c/db_set_flags.html#DB_REVSPLITOFF

Regards,
Michael.

Claus Jensen · *nix forums beginner Joined: 21 Mar 2005 Posts: 5

Thank you for your answer.

In addition we have a question with regards to nature of the implemented
b+tree structure. With regards to the traditional b+tree theory, nodes may
be coalesced upon deleting data entries from the leafnodes. However. looking
at the tree structure in Berkeley DB, we have noticed that this does not
seem to be the case for this database.

However, we have noticed in the code comments that something called a
"reversed split" exists. Is this similar to the case where we combine nodes
or does Berkeley not support this?

If it does support this, is it then something we can switch on and off? (we
are asking because it appears from the code comments that this is possible)

Thanks
Claus

<ubell@sleepycat.com> wrote in message
news:1112026660.963621.165330@o13g2000cwo.googlegroups.com...

ubell@sleepycat.com · *nix forums beginner Joined: 06 Jun 2005 Posts: 49

Berkeley DB supports b+trees in that the key/data pairs are stored
in the leaf nodes.

Michael Ubell
Sleepycat Software.

Claus Jensen · *nix forums beginner Joined: 21 Mar 2005 Posts: 5

Hi,

could someone please confirm whether the btree in Berkeley DB is a regular
btree or a b+tree?

Rgds
Claus

Google