RE: RE: How does Oracle keep B-tree indexes to 3 levels?

From: Powell, Mark D <mark.powell_at_eds.com>
Date: Thu, 19 Feb 2004 09:56:14 -0500
Message-ID: <564DE4477544D411AD2C00508BDF0B6A1CE0A9FB@USAHM018.amer.corp.eds.com>

OK, What is the high level difference between a B*Tree and a B+Tree? When I was in college I remember discussions on Btrieve and (Balanced) Binary trees, where each node has at most two children. The terminology seems to have changed over the years. Fortunately we never got to Red/Black trees and a couple of other variations.

-----Original Message-----

From: oracle-l-bounce_at_freelists.org
[mailto:oracle-l-bounce_at_freelists.org]On Behalf Of Jonathan Lewis Sent: Thursday, February 19, 2004 4:34 AM To: oracle-l_at_freelists.org
Subject: Re: RE: How does Oracle keep B-tree indexes to 3 levels?

It is possible that the 67% you are quoting is the figure given for the worst-case scenario on b*trees, which is textbook stuff. (Although Oracle claims B*Trees in their manuals somewhere, they aren't using them, they are using B+trees).

The 69% comes from a paper on Fringe Analysis of 2-3 trees, and is a result that applies to generic b-trees.

Of course, it is possible that you were at college many years after I was, so fringe analysis may be a standard on the sylllabus now.

Regards

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

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 Thu Feb 19 2004 - 08:56:14 CST