CREATE INDEX - Balanced Tree (B-Tree)

Balanced Tree (B-Tree)

Açıklaması şöyle

The B-Tree index type uses a balanced tree structure to speed up equality and range queries on columns of all data types. Since B-Tree index entries are sorted, they are sometimes used to retrieve table rows in order, thereby avoiding manually sorting them after retrieval.

This is the default index type and also the most commonly used.

B+ Tree vs B Tree

Açıklaması şöyle. Yani B Tree dense bile aslında PostgreSQL B+ Tree kullanıyor

Postgresql has an index with the type “B-tree” which is implemented based on B-tree. More specifically, on one of its variations — B-tree+ (keys to rows are stored only in leaf nodes).

Açıklaması şöyle

The most common index used in a relational database system is the B+ Tree one. Like the B-Tree index, the B+ Tree is a self-balanced ordered tree data structure.

Both the B-Tree and the B+Tree start from a Root node and may have Internal Nodes and Leaf Nodes. However, unlike the B-Tree, the B+ Tree stores all the keys in the leaf nodes, and the adjacent Leaf nodes are linked via pointers, which simplifies range scans.

Without an index, whenever we are looking for a given column value, we’d need to scan all the table records and compare each column value against the provided one. The larger the table, the more pages will have to be scanned in order to find all the matching records.

On the other hand, if the column value is highly selective (e.g., a small number of records match that column value), using a B+Tree index allows us to locate a column value much faster since fewer pages will be needed to be scanned.

Page Büyüklüğü

Açıklaması şöyle. 8 KB büyüklüğünde. Bu da büyük bir M sayısının oluşmasına sebep oluyor

As mentioned in the post, each node is located on one block (page in terms of PostgreSQL, usually 8KB). In practice, a node contains a lot (M = hundreds) keys. As a result, the depth (number of levels) of the B-Tree is quite small, about 4–5 for very large tables. Just imagine, B-tree allows us to get a needed key by using only 4–5 disk read operations.

Şeklen şöyle. Burada M = 3 ve row bilgisi son yaprak ta saklanıyor.

Search bu equality şeklen şöyle

Search by range şeklen şöyle. N>=11 olan tüm değerleri arıyoruz. Arama hep sağa doğru gidiyor

Kullanım

Örnek
Şöyle yaparız.

CREATE INDEX idx ON adsets (date, platform);

Örnek
Şöyle yaparız. Burada USING BTREE ile indeksin tipi belirtiliyor. Normalde gerekli değil

CREATE INDEX id_idx ON fake_data USING BTREE(id);

Bu index aynı zamanda pattern_ops ile de kullanılabilir. 

- text_pattern_ops : text için

- varchar_pattern_ops : varchar için

- bpchar_pattern_ops : char için

değerlerini alabilir.

PostgreSQL'de Primary Index Yoktur

MySQL'de secondary index satırın tüm verisini içeren bir primary index'e işaret eder. PostgreSQL böyle değil. Direkt heap'teki bir yere işaret eder. Şeklen şöyle.