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