Wikibooks: PostgreSQL/Index Btree

• Format: Book
• Language: English
• Subjects: The Pointers
• Online Access: https://en.wikibooks.org/wiki/PostgreSQL/Index_Btree

Nav The term B tree index denotes the implementation of a . B trees are characterized by the criterion that the distance from the root node to every leaf node is the same. Such trees support the very fast evaluation of search criteria like WHERE status=5 . In most cases such trees have a high branching factor and hence a low depth. If for example there is a branching factor of 500 the tree can manage about 125 million entries with 3 page reads. In addition the PostgreSQL implementation optimizes the locking behavior of concurrent write operations to the tree with a strategy that was originally proposed by . The idea is to add additional (redundant as of the perspective of the complete tree) pointers to every page. = SQL syntax = B tree is the default index type. It is created by the SQL command CREATE INDEX when the keyword USING is omitted. create a b tree index CREATE INDEX test idx ON table 1 (column 1) equivalent syntax CREATE INDEX test idx ON table 1 USING BTREE(column 1) = Description = The file containing the B tree consists of different page types. The very first page (#0) of the file holds meta information about the index e.g. the pointer to the root page which is not always located on page #1 or the current tree depth. Internal pages contain pairs of keys and pointers. Keys hold the values which shall be indexed and the pointers point to internal pages of the next level or to leaf pages. Those pairs are denoted index entries . Leaf pages contain such pairs as well. But in this case they point to pages and rows in the data file (heap). Such pointers are called TupleId s or TID s. Internal pages plus leaf pages constitute the B tree. Over time pages need to be split because their capacity gets exhausted. First the tree grows in breadth. In rare cases it gets necessary that the high of the tree must be extended. In this case the root page gets split and a new root page is created. There are some special rules to optimize the access to B trees especially to reduce the probability of locks in a multiuser ...