Re: B+Tree vs. B*Tree

From: Jonathan Lewis <jonathan_at_jlcomp.demon.co.uk>
Date: Sat, 7 Feb 2004 11:21:26 -0000
Message-ID: <017701c3ed6c$890409e0$6702a8c0@Primary>

I'm talking outside my area of expertise here, so don't take this as guaranteed:

B+
When a leaf block is full it splits and half the contents will be moved to the new leaf. (In fact Steve Adams has demonstrated that Oracle tries to optimise branch packing by being a little flexible on the split).

B*
When a leaf block is full, you scan the two adjacent leaf blocks to see if you can migrate one entry into them. If this is not possible, you split two buckets into three. (I don't know how you choose whether to split the left or right neighbour).

B+ can run down to 50% efficiency on random inserts, whereas B+ can only go down to 67%.

B* has to do more work more often on inserts. (In Oracle's case it might also be much more expensive when dealing with read-consistent queries).

Regards

Jonathan Lewis
http://www.jlcomp.demon.co.uk

  The educated person is not the person
  who can answer the questions, but the
  person who can question the answers -- T. Schick Jr

Next public appearances:
March 2004 Hotsos Symposium - The Burden of Proof March 2004 Charlotte NC OUG - CBO Tutorial April 2004 Iceland

One-day tutorials:
http://www.jlcomp.demon.co.uk/tutorial.html

Three-day seminar:
see http://www.jlcomp.demon.co.uk/seminar.html
____UK___February
____UK___June

The Co-operative Oracle Users' FAQ
http://www.jlcomp.demon.co.uk/faq/ind_faq.html

Original Message ----- From: "Daniel Hanks" <hanksdc_at_about-inc.com> To: <oracle-l_at_freelists.org> Sent: Friday, February 06, 2004 8:08 PM Subject: B+Tree vs. B*Tree

This may be a little off-topic, but, what are the differences between B+tree indexes, and B*tree indexes? At school I had to write a program to perform insert and update on a B+tree index, so I'm familiar with that type of index. Searching for B*tree on Google is less than effective as Google strips out the * character.

Any docs you could point me to would be helpful. I have the Silberschatz book mentioned previously today, which covers B-tree, and B+tree indexes, but not b*tree indexes.

Thanks,

Dan
Daniel Hanks - Systems/Database Administrator About Inc., Web Services Division

Please see the official ORACLE-L FAQ: http://www.orafaq.com

To unsubscribe send email to: oracle-l-request_at_freelists.org put 'unsubscribe' in the subject line.

--
Archives are at http://www.freelists.org/archives/oracle-l/
FAQ is at http://www.freelists.org/help/fom-serve/cache/1.html
-----------------------------------------------------------------

Received on Sat Feb 07 2004 - 05:21:26 CST