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 -- Sent via pgsql-general mailing list (pgsql-general@xxxxxxxxxxxxxx) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-general
