Performance of PostgreSQL B+-tree algorithm

From: Kyle Lanclos <lanclos(at)ucolick(dot)org>
To: pgsql-general(at)postgresql(dot)org
Subject: Performance of PostgreSQL B+-tree algorithm
Date: 2012-05-14 18:10:30
Message-ID: 20120514181030.GC10214@monkey.ucolick.org
Views: Raw Message | Whole Thread | Download mbox | Resend email
Thread:
Lists: pgsql-general

I spent some time last week staring at the code for the PostgreSQL
B+-tree implementation. What I hoped to find, and was not immediately
able to determine, was the Knuth order for the PostgreSQL B+-tree
implementation. It is entirely possible that I simply got lost in the
wrong C file.

My goal is to make an informed assertion about the performance of
a PostgreSQL B+-tree index as the quantity of records in our database
grows more or less unbounded.

To use a common reference, wikipedia states the following:

Bayer & McCreight (1972), Comer (1979), and
others define the order of B-tree as the
minimum number of keys in a non-root node.
Folk & Zoellick (1992) points out that terminology
is ambiguous because the maximum number of keys
is not clear. An order 3 B-tree might hold a
maximum of 6 keys or a maximum of 7 keys.
(Knuth 1998, p. 483) avoids the problem by defining
the order to be maximum number of children (which
is one more than the maximum number of keys).

http://en.wikipedia.org/wiki/B-tree

I would be happy to refer to an academic publication if it contains a
clear analysis of the PostgreSQL B+-tree implementation.

Thanks much,

--Kyle

Responses

Browse pgsql-general by date

  From Date Subject
Next Message François Beausoleil 2012-05-14 18:36:13 Re: COPY from CSV, passing in default value?
Previous Message EllyR 2012-05-14 17:58:42 Re: Move the postgreSQL database from Drive C to Map Network Drive (Called Z)