Re: B+Tree vs. B*Tree
- From: "Jonathan Lewis" <jonathan@xxxxxxxxxxxxxxxxxx>
- To: <oracle-l@xxxxxxxxxxxxx>
- Date: Sat, 7 Feb 2004 11:21:26 -0000
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@xxxxxxxxxxxxx>
To: <oracle-l@xxxxxxxxxxxxx>
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@xxxxxxxxxxxxx
put 'unsubscribe' in the subject line.
--
Archives are at //www.freelists.org/archives/oracle-l/
FAQ is at //www.freelists.org/help/fom-serve/cache/1.html
-----------------------------------------------------------------
Other related posts:
