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.

Sorted Olması

Açıklaması şöyle

Your Postgres table was fast for months. Then one week, inserts that took 1ms started taking 10ms, autovacuum couldn't keep up, and nothing in your code changed.

Here's the part most people get wrong about why: it's not because "Postgres doesn't scale." It's because Postgres's indexes are B-Trees, and every B-Tree index has to stay sorted, on every single write. Two indexes on a table means one cheap heap append plus two separate random writes, every insert. Update a row (thanks to MVCC), and you pay that same cost again, plus a dead tuple autovacuum has to clean up later.

Cassandra and friends made the opposite bet: an LSM-Tree engine that never sorts anything at write time; it just appends and sorts later in the background (compaction). Writes stay fast forever. The cost shows up on reads instead.

Neither engine is "better." They're both just honouring a trade they made before you wrote a single query. I wrote up the mechanics, the actual production symptoms each one causes, and when "just switch databases" is the wrong fix.

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.