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
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) |