10

I am learning about postgresql internals and I am wondering or postgresql B-tree index is actually classic B-tree or B+tree? To spell it out, that means the nodes contain only keys or key-value pairs?

Borys
  • 2,676
  • 2
  • 24
  • 37

2 Answers2

9

I said B-trees, first, but it's arguably closer to B+ trees.
See iwis' answer discussing it more thoroughly.

You would really have to consider index + heap (+ auxiliary storage) together. An index is mostly useless on its own.

Here is a related chapter on Wikipedia.

The name of the relevant index method is "B-tree" in Postgres. Physical storage is very similar to that of tables (the heap) or any other index type. All use the same data pages with mostly the same page-layout. More in the manual.

Development is ongoing. The design has been changed (improved) in many aspects since this question was asked. The latest notable change (as of April 2021) being deduplication in Postgres 13.

Erwin Brandstetter
  • 605,456
  • 145
  • 1,078
  • 1,228
  • 3
    but if db stores only keys it would be B+? – Borys Jul 28 '14 at 22:40
  • 4
    A b+ tree would store data in the leaves. The distinction between b and b+ tree does not make much sense for indexes to begin with. Index and table together form a special form of a b+ tree, if you will. The index itself is just a b-tree. – Erwin Brandstetter Jul 28 '14 at 22:44
  • @ErwinBrandstetter Do you mean that index in postgres are just a b-tree whose leaf node contains pointers to actual data stored in disk. – a.m. Sep 06 '14 at 05:46
  • @a.m.: Something in between. The index contains the columns listed in the definition plus a pointer to the row, which is the complete "value". – Erwin Brandstetter Sep 06 '14 at 11:27
  • @ErwinBrandstetter : Thanks for clearing, If possible for you Can you please ans 1 of my que(kind of related/similar) http://stackoverflow.com/questions/25662145/why-there-is-a-performance-difference-between-single-column-select-and-multi-col/25674646#25674646 – a.m. Sep 07 '14 at 08:00
  • @ErwinBrandstetter Doesn't this make it still a B+-tree if you consider the pointer to the row data as well? (Which I would because the pointer is not a key...) – r0estir0bbe Jan 25 '16 at 14:09
  • @r0estir0bbe: It's hard to draw the line. The distinction between "key" and "value" is not clear to begin with. What's a "key" to one query is the "value" to another. And there are also index-only scans, which use the index in B+ tree fashion, obviously. The classic use case is that the index stores keys and points to rows in the table holding values. – Erwin Brandstetter Jan 25 '16 at 14:16
  • @ErwinBrandstetter: To me, your answer sounds very cut/black & white - that is the reason why I was confused. Thanks for clarifying! – r0estir0bbe Jan 25 '16 at 15:08
  • 6
    the discussion about 'data' is confusing people and isn't significant. The best way to understand the distinction is that in a naive b+tree, keys in internal nodes will be repeated in the leaves, while in a b-tree, if the key is stored in an internal node, it will not also be stored in a leaf. It's absolutely the case that b+trees are often used as indicies where the 'data' portion is a reference to the full record. The big advantage of a b+tree is simply that because everything is stored in leaves, you can make the leaves into a linked list and have very fast iteration of range queries. – kybernetikos Apr 10 '17 at 20:10
  • @ErwinBrandstetter: When Borys asked if the nodes also contain values, he meant whether non-leaf nodes contain pointers to records in the indexed table, because this is the difference between B-tree and B+ tree. It seems that non-leaf nodes don't have such pointers in PostgreSQL, so PostgreSQL seems to use B+ tree - please see my answer. – iwis Apr 25 '21 at 12:22
8

It seems to me that PostgreSQL uses B+ tree.

The difference between B-tree and B+ tree

  • In B-tree the pointers to records in the indexed table are not only in the leaves of the tree, but also in all internal nodes of the tree.
  • In B+ tree the pointers to records in the indexed table are only in the leaves of the tree. The advantages of B+ tree over B-tree are described here.

the picture is a modification (the picture is a modification of this picture)

Usage of B+ tree in DBMSs

Oracle, SQL Server, SQLite, DB2, and MySQL use B+ tree. It seems that also PostgreSQL uses B+ tree because:

  • The documentation seems to state that only the leaves of the tree have the pointers to records in the indexed table:

    Each leaf page contains tuples that point to table rows. Each internal page contains tuples that point to the next level down in the tree.

  • When Bruce Momjian says about internal nodes he doesn't mention that they have pointers to records in the indexed table.

  • The src/backend/access/nbtree/README file of the PostgreSQL source code mentioned in the documentation contains this comment:

    Btree Indexing

    This directory contains a correct implementation of Lehman and Yao's high-concurrency B-tree management algorithm (P. Lehman and S. Yao, Efficient Locking for Concurrent Operations on B-Trees, ACM Transactions on Database Systems, Vol 6, No. 4, December 1981, pp 650-670).

    Lehman and Yao use a tree structure named B* tree, which was defined by Wedekind in On the selection of access paths in a data base system paper as B-tree where non-leaf nodes don't have pointers to records in the indexed table (they have pointers only to their children nodes). So the B* tree structure defined by Wedekind is a B+ tree.

iwis
  • 1,382
  • 1
  • 13
  • 26
  • I agree, the implementation is closer to a B+ tree. But the discussion does not make a whole lot of sense to begin with. You would really have to consider index and heap (and toast table and other auxiliaries) together. – Erwin Brandstetter Apr 25 '21 at 12:42