Introdução

O Pages e Storage Layout terminou com um heap: as linhas ficam em qualquer página que tinha espaço, e cada uma tem um endereço tipo (7,3). Isso serve para guardar linhas e não serve para nada na hora de encontrá-las. Para responder WHERE id = 42 num heap, você lê todas as páginas.

Todo engine relacional conhecido resolve isso com a mesma estrutura, a B-tree, e faz isso há uns cinquenta anos. O índice padrão do PostgreSQL, as tabelas e índices do SQLite e as tabelas clustered do InnoDB são todos B-trees montadas com as slotted pages do artigo anterior. Este aqui mostra por que a árvore tem esse formato, como ela cresce por meio de splits de página, e como isso aparece dentro de um índice real do PostgreSQL.

Uma árvore binária no disco é alta demais

A Parte 2 de Data Structures with Golang construiu uma BinarySearchTree e uma AVLTree, e a última seção dela citava as B-trees entre as variações que partem das mesmas ideias. É aqui que ela entra. A regra de busca é a da BST, chaves menores à esquerda e maiores à direita, e como a AVL tree ela continua balanceada seja qual for a ordem dos inserts. O que muda é o formato, porque agora a árvore precisa morar no disco.

Uma AVL tree com um milhão de chaves tem uns 20 níveis, já que log2(1.000.000) dá mais ou menos 20. Na memória isso são 20 saltos de ponteiro e ninguém percebe.

No disco, cada um desses saltos pode ser uma leitura de página. Vinte leituras aleatórias por lookup é lento num SSD e péssimo num HD, e a maior parte de cada leitura de 8 KB seria desperdiçada: um nó binário guarda uma chave e dois ponteiros, talvez 24 bytes da página.

A solução é fazer cada nó ocupar uma página. Se uma página guarda algumas centenas de chaves e algumas centenas de ponteiros para filhos, cada nível divide o espaço de busca por algumas centenas em vez de por dois:

Um índice do PostgreSQL numa coluna int cabe umas 400 entradas por página, então uma tabela de um bilhão de linhas tem quatro níveis. Os dois níveis de cima são um punhado de páginas lidas em todo lookup, que ficam no buffer pool o tempo todo. Na prática, um lookup pontual custa uma ou duas leituras de página que realmente erram o cache, não importa o tamanho da tabela.

Essa é a ideia toda da B-tree. É uma árvore de busca balanceada cujos nós são páginas, largos o suficiente para a árvore continuar baixa.

B-tree ou B+tree

A B-tree original de Bayer e McCreight (1970) guarda chaves e valores em todos os nós. Quase todo banco de dados usa na verdade a variante chamada B+tree:

• Páginas folha guardam todas as chaves, cada uma com seu valor. Num índice do PostgreSQL o valor é o ctid no heap; nas árvores de tabela do SQLite é a própria linha.
• Páginas internas guardam só chaves separadoras e números de páginas filhas. Um separador só diz qual filho seguir, e não precisa ser uma chave que ainda existe.
• As folhas são ligadas às irmãs, então um range scan acha a primeira chave e depois anda de lado pelo nível das folhas sem subir de novo.

Deixar os valores fora das páginas internas é o que deixa o fanout alto. Uma página interna cheia de chaves de 4 bytes e números de página de 4 bytes cabe muito mais entradas do que uma que também carrega linhas. Os links entre irmãs são o que deixa BETWEEN, ORDER BY e > baratos: achado o começo, o resto é ler folhas em ordem. É justamente o que a hash table da Parte 3 não te dá: ela acha uma chave em O(1), mas WHERE id BETWEEN 100 AND 200 significa olhar todos os buckets.

A maioria dos papers e do código-fonte diz só "B-tree" querendo dizer B+tree, e o resto deste artigo faz o mesmo.

Uma B+tree em Go

Aqui vai uma B+tree pequena. Os nós são identificados por um PageID e buscados num map, que faz o papel do buffer pool do artigo anterior, e MaxKeys vale 4 para os splits acontecerem com frequência suficiente para a gente acompanhar. Um engine de verdade serializaria cada nó numa slotted page. A árvore também implementa a mesma interface Container usada em toda a série de Data Structures, então ela fica lado a lado com a BinarySearchTree e a AVLTree.

package btree

import (
	"fmt"
	"math"
	"slices"
)

// MaxKeys is tiny so splits are easy to watch. A real 8 KB page holds hundreds.
const MaxKeys = 4

type PageID uint32

type node struct {
	leaf     bool
	keys     []int64
	children []PageID // internal: len(keys)+1 child pages
	values   []string // leaf: one value per key
	next     PageID   // leaf: right sibling, 0 = none
}

type Tree struct {
	pages  map[PageID]*node // stands in for the buffer pool
	root   PageID
	nextID PageID
	size   int
}

func New() *Tree {
	t := &Tree{pages: map[PageID]*node{}, nextID: 1}
	t.root = t.alloc(&node{leaf: true})
	return t
}

func (t *Tree) alloc(n *node) PageID {
	id := t.nextID
	t.nextID++
	t.pages[id] = n
	return id
}

// childIndex picks the child to follow. keys[i] separates children[i]
// (everything < keys[i]) from children[i+1] (everything >= keys[i]).
func childIndex(keys []int64, key int64) int {
	i, found := slices.BinarySearch(keys, key)
	if found {
		return i + 1
	}
	return i
}

func (t *Tree) findLeaf(key int64) *node {
	n := t.pages[t.root]
	for !n.leaf {
		n = t.pages[n.children[childIndex(n.keys, key)]]
	}
	return n
}

func (t *Tree) Get(key int64) (string, bool) {
	n := t.findLeaf(key)
	i, found := slices.BinarySearch(n.keys, key)
	if !found {
		return "", false
	}
	return n.values[i], true
}

// Scan calls fn for every key in [from, to], following leaf siblings.
func (t *Tree) Scan(from, to int64, fn func(int64, string)) {
	for n := t.findLeaf(from); n != nil; n = t.pages[n.next] {
		for i, k := range n.keys {
			if k > to {
				return
			}
			if k >= from {
				fn(k, n.values[i])
			}
		}
	}
}

func (t *Tree) Empty() bool { return t.size == 0 }

func (t *Tree) Size() int { return t.size }

func (t *Tree) Clear() { *t = *New() }

// Values walks the leaf level left to right, so keys come out sorted.
func (t *Tree) Values() []interface{} {
	values := make([]interface{}, 0, t.size)
	t.Scan(math.MinInt64, math.MaxInt64, func(k int64, _ string) {
		values = append(values, k)
	})
	return values
}

func (t *Tree) String() string {
	return fmt.Sprintf("%v", t.Values())
}

Um lookup é uma busca binária dentro de cada página, da raiz até uma folha. Cada nível é uma visita a uma página, então o custo do Get é a altura da árvore. O Scan desce uma vez para achar onde from estaria e nunca mais sobe: lê o resto daquela folha e segue o next até passar de to.

O Values é onde a diferença para a Parte 2 aparece. Lá, o bstInOrder descia recursivamente na subárvore esquerda, visitava o nó e descia na direita para produzir a saída ordenada. Uma B+tree guarda todas as chaves nas folhas, já ordenadas e ligadas, então o percurso in-order vira um loop pelo nível de baixo. Com as mesmas chaves do exemplo de BST da Parte 2:

t := btree.New()
for _, k := range []int64{8, 3, 10, 1, 6, 14, 4, 7, 13} {
	t.Put(k, "")
}
fmt.Println(t.Size(), t.Height()) // 9 2
fmt.Println(t)                    // [1 3 4 6 7 8 10 13 14]

A BST precisou de quatro níveis para essas nove chaves. Com quatro chaves por página, a B+tree precisa de dois.

Inserindo e fazendo split

A inserção sempre acontece numa folha. O caso interessante é quando a folha já está cheia:

// Put inserts or replaces key. When the root splits, the tree grows by one level.
func (t *Tree) Put(key int64, value string) {
	if sep, right, split := t.insert(t.root, key, value); split {
		t.root = t.alloc(&node{keys: []int64{sep}, children: []PageID{t.root, right}})
	}
}

// insert returns the separator and new right page when id had to split.
func (t *Tree) insert(id PageID, key int64, value string) (int64, PageID, bool) {
	n := t.pages[id]
	if n.leaf {
		i, found := slices.BinarySearch(n.keys, key)
		if found {
			n.values[i] = value
			return 0, 0, false
		}
		n.keys = slices.Insert(n.keys, i, key)
		n.values = slices.Insert(n.values, i, value)
		t.size++
	} else {
		i := childIndex(n.keys, key)
		sep, right, split := t.insert(n.children[i], key, value)
		if !split {
			return 0, 0, false
		}
		n.keys = slices.Insert(n.keys, i, sep)
		n.children = slices.Insert(n.children, i+1, right)
	}
	if len(n.keys) <= MaxKeys {
		return 0, 0, false
	}
	return t.split(n)
}

func (t *Tree) split(n *node) (int64, PageID, bool) {
	mid := len(n.keys) / 2
	sep := n.keys[mid]
	r := &node{leaf: n.leaf}
	if n.leaf {
		// Leaf: the separator is copied up and stays in the right page.
		r.keys = slices.Clone(n.keys[mid:])
		r.values = slices.Clone(n.values[mid:])
		n.keys, n.values = n.keys[:mid], n.values[:mid]
		r.next = n.next
	} else {
		// Internal: the separator moves up and leaves both halves.
		r.keys = slices.Clone(n.keys[mid+1:])
		r.children = slices.Clone(n.children[mid+1:])
		n.keys, n.children = n.keys[:mid], n.children[:mid+1]
	}
	rid := t.alloc(r)
	if n.leaf {
		n.next = rid
	}
	return sep, rid, true
}

Quando uma folha estoura, metade das chaves vai para uma página nova, e a primeira chave da página nova sobe para o pai como separador. Se isso fizer o pai estourar, ele também faz split, e assim por diante para cima. Quando a própria raiz faz split, o Put cria uma raiz nova acima das duas metades. Esse é o único jeito de uma B-tree ficar mais alta.

Compara isso com o insertAVL da Parte 2. A AVL tree adiciona um nó embaixo, recalcula as alturas no caminho de volta e faz rotação quando um lado fica dois níveis mais alto que o outro. Uma B-tree nunca rotaciona. Ela cresce pela raiz em vez de pelas folhas, então toda folha está sempre na mesma profundidade e não existe fator de balanceamento para acompanhar. A recursão é conhecida, porém: o insert devolve o split para quem chamou do mesmo jeito que o insertAVL devolve uma nova raiz de subárvore.

Inserir 5 numa folha cheia fica assim:

Split de folha e split interno são um pouco diferentes. O split de folha copia o separador para cima e mantém o 3 na folha da direita, porque o nível das folhas precisa ter todas as chaves. O split interno move o separador do meio para cima e tira ele das duas metades, já que ele só existe para rotear buscas.

Usando:

t := btree.New()
for i := int64(1); i <= 20; i++ {
	t.Put(i, fmt.Sprintf("user-%d", i))
}
fmt.Println(t.Height()) // 3

t.Scan(7, 10, func(k int64, v string) { fmt.Print(v, " ") })
// user-7 user-8 user-9 user-10

Agora olha o quanto as folhas ficam cheias. Insere 100.000 chaves em ordem crescente numa árvore e as mesmas chaves em ordem aleatória em outra, e conta quantos dos MaxKeys slots de cada folha estão em uso:

sequential: 50% full, random: 73% full

Entrada ordenada também era o caso ruim na Parte 2, onde transformava uma BST simples numa lista ligada. A altura de uma B-tree não degenera desse jeito, então aqui a entrada ordenada custa espaço. Todo split acontece na folha mais à direita, deixa a metade esquerda com 2 chaves, e nada nunca mais é inserido naquela página da esquerda. Inserts aleatórios caem pela árvore inteira e voltam a encher as páginas entre um split e outro, por isso ficam em torno de 70%. Engines de verdade tratam o caso crescente de forma especial, como vamos ver agora.

Dentro de uma B-tree do PostgreSQL

A B-tree do PostgreSQL se chama nbtree, e o código fica em src/backend/access/nbtree/. O README desse diretório é o documento de design, e vale ler inteiro depois de terminar este artigo. Vamos criar um índice e abrir:

CREATE EXTENSION pageinspect;
CREATE TABLE seq (id int PRIMARY KEY);
INSERT INTO seq SELECT generate_series(1, 1000000);

SELECT root, level FROM bt_metap('seq_pkey');

 root | level
------+-------
  412 |     2

O bloco 0 de todo índice nbtree é uma metapage que registra onde a raiz está. A raiz está no bloco 412, dois níveis acima das folhas (nível 0), então a árvore tem três níveis. A raiz pode mudar de lugar quando faz split, e a metapage é como toda busca encontra ela. Um milhão de linhas, três níveis.

Agora uma folha. O bt_page_stats lê o header da página e o special space, os 16 bytes de BTPageOpaqueData no fim da página que o artigo anterior disse que as páginas de B-tree usam para os links entre irmãs:

SELECT type, live_items, free_size, btpo_prev, btpo_next, btpo_level
FROM bt_page_stats('seq_pkey', 1);

 type | live_items | free_size | btpo_prev | btpo_next | btpo_level
------+------------+-----------+-----------+-----------+------------
 l    |        367 |       808 |         0 |         2 |          0

O bloco 1 é a folha mais à esquerda (btpo_prev é 0), a irmã da direita é o bloco 2, e ele guarda 367 itens. Cada item é um IndexTupleData: um TID de heap de 6 bytes, 2 bytes de flags e tamanho, e a chave de 4 bytes, com padding até 16 bytes, mais um line pointer de 4 bytes. São 20 bytes por entrada, então (8192 - 24 - 16) / 20 dá um máximo de umas 407 por página. A página está só 90% cheia, e isso é de propósito.

SELECT itemoffset, ctid, itemlen, data
FROM bt_page_items('seq_pkey', 1) LIMIT 3;

 itemoffset | ctid  | itemlen |          data
------------+-------+---------+-------------------------
          1 | (1,1) |      16 | 6f 01 00 00 00 00 00 00
          2 | (0,1) |      16 | 01 00 00 00 00 00 00 00
          3 | (0,2) |      16 | 02 00 00 00 00 00 00 00

Do item 2 em diante são as entradas do índice: a chave 1 aponta para a tupla (0,1) do heap, a chave 2 para (0,2), em bytes little-endian. O item 1 não é uma entrada. É a high key da página, 0x16f = 367, um limite superior para qualquer chave que a página possa conter. Toda folha menos a mais à direita tem uma, e é ela que torna seguros os splits concorrentes, como vamos ver mais abaixo.

A raiz mostra a outra metade do formato:

SELECT itemoffset, ctid, itemlen, data
FROM bt_page_items('seq_pkey', 412) LIMIT 3;

 itemoffset |  ctid   | itemlen |          data
------------+---------+---------+-------------------------
          1 | (3,0)   |       8 |
          2 | (411,1) |      16 | 77 97 01 00 00 00 00 00
          3 | (698,1) |      16 | ed 2e 03 00 00 00 00 00

Nas páginas internas o campo ctid guarda o número de um bloco filho em vez de um endereço no heap. O primeiro item não tem chave nenhuma: ele significa "menos infinito", e aponta para o bloco 3 para tudo que vem antes do próximo separador. O segundo diz que chaves a partir de 0x19777 (104.311) vão para o bloco 411. É o mesmo layout do childIndex da versão em Go, com um filho a mais do que separadores.

Um lookup pontual toca uma página por nível mais o heap:

EXPLAIN (ANALYZE, BUFFERS, COSTS OFF, TIMING OFF)
  SELECT * FROM seq WHERE id = 500000;

 Index Only Scan using seq_pkey on seq (actual rows=1.00 loops=1)
   Index Cond: (id = 500000)
   Heap Fetches: 1
   Index Searches: 1
   Buffers: shared hit=4

Quatro buffers: raiz, página interna, folha e uma página do heap. O heap fetch acontece porque a tabela ainda não passou por VACUUM, então o visibility map não consegue garantir a linha; depois de um VACUUM, isso vira três.

A página mais à direita faz split diferente

Os 90% vêm do _bt_findsplitloc em nbtsplitloc.c. Quando a página que está fazendo split é a mais à direita do nível, a nbtree assume que os inserts são crescentes e divide de forma que a página da esquerda fique com fillfactor por cento dos dados: 90 para folhas por padrão, 70 para páginas internas. Todo o resto divide mais ou menos no meio. O CREATE INDEX também enche as folhas até 90% quando monta o índice a partir de dados ordenados.

Essa é a solução para os 50% que a nossa árvore em Go tem com chaves sequenciais. IDs serial, timestamps e outras chaves crescentes enchem as páginas quase por completo e nunca mais tocam nelas. O SQLite tem o mesmo truque para tabelas: o balance_quick em btree.c trata um append na folha mais à direita colocando a linha nova sozinha numa página nova e deixando a página cheia como está.

Split sem parar os leitores

A nossa árvore em Go assume que nada mais roda durante um split. No PostgreSQL, centenas de backends podem estar lendo e inserindo no mesmo índice, e você não quer que um split tranque todo mundo fora do caminho da raiz até a folha.

A nbtree usa o design do paper de Lehman e Yao de 1981, e é por isso que toda página tem um link para a irmã da direita e uma high key. Uma busca lê o pai, solta o pai, e depois lê o filho. Entre esses dois passos o filho pode fazer split e mandar a chave procurada para uma irmã nova à direita. Então, quando a busca chega no filho, ela compara a chave com a high key. Se a chave for maior, a página fez split por baixo dela, e a busca segue o link da direita, quantas vezes precisar. Leitores nunca seguram mais de um lock de página por vez enquanto descem.

Os splits acontecem em dois passos. Primeiro a página é dividida e a irmã nova da direita é ligada, tudo num único registro de WAL. Depois o separador da página nova é inserido no pai, num passo separado. Se o servidor cair entre os dois, a página da esquerda fica com a flag BTP_INCOMPLETE_SPLIT, e o próximo insert que passar por ela termina o serviço. Enquanto isso nada se perde, porque qualquer busca que chegue na página da esquerda ainda acha a da direita pelo link entre irmãs.

Duplicatas e posting lists

Uma primary key tem uma entrada por valor. Um índice em status com cinco valores distintos tem 200.000 entradas por valor, e guardar a mesma chave 200.000 vezes é quase tudo desperdício. Desde o PostgreSQL 13, a nbtree faz deduplicação delas em posting lists: uma chave seguida de um array ordenado de TIDs do heap.

CREATE TABLE orders (id int, status int);
INSERT INTO orders SELECT i, i % 5 FROM generate_series(1, 1000000) i;
CREATE INDEX orders_status ON orders (status);
CREATE INDEX orders_status_nodedup ON orders (status) WITH (deduplicate_items = off);

 orders_status | orders_status_nodedup
---------------+-----------------------
 6800 kB       | 21 MB

Três vezes menor, com o mesmo número de linhas indexadas. O bt_page_items mostra as posting lists como itens de 808 bytes com um array tids. A deduplicação roda de forma preguiçosa, só quando uma folha está prestes a fazer split, então não custa nada em páginas que ainda têm espaço. Índices únicos também ganham, porque o MVCC deixa várias versões da mesma chave por aí até o vacuum passar, assunto de um artigo mais para frente.

O PostgreSQL 12 também trouxe suffix truncation: quando uma folha faz split, o separador novo guarda só as colunas iniciais necessárias para distinguir as duas páginas. Num índice (customer_id, created_at), os separadores das páginas internas muitas vezes têm só o customer_id, o que faz as páginas internas caberem mais entradas e a árvore ficar mais baixa.

Páginas não se juntam

Split não tem o caminho de volta na nbtree. O VACUUM remove entradas mortas das folhas, e só apaga uma página quando ela está completamente vazia. Duas folhas vizinhas com 10% cada continuam sendo duas páginas.

Essa é a fonte comum de bloat em índice. Uma tabela onde a maioria das linhas vai sendo apagada com o tempo, ou uma com uma faixa quente de chaves que vive sendo atualizada, acaba com um índice bem maior que os dados vivos. O bottom-up deletion do PostgreSQL 14 ajuda no caso de updates, limpando versões antigas de linhas de uma folha antes de fazer split nela, mas não consegue juntar páginas que já estão meio vazias. A solução é reescrever, e o REINDEX INDEX CONCURRENTLY faz isso sem bloquear escritas.

O custo de chaves aleatórias

Insere o mesmo milhão de inteiros em ordem aleatória em vez de crescente:

CREATE TABLE rnd (id int PRIMARY KEY);
INSERT INTO rnd SELECT i FROM generate_series(1, 1000000) i ORDER BY random();

 index    | leaf_pages | avg_leaf_density | size
----------+------------+------------------+-------
 seq_pkey |       2733 |            90.01 | 21 MB
 rnd_pkey |       3761 |            65.48 | 30 MB

Mesmas chaves, 40% mais páginas. Inserts aleatórios fazem split de páginas no meio pela árvore inteira, e as páginas ficam em torno de dois terços cheias, que é o que a nossa árvore em Go também mostrou. Esses números vêm do pgstatindex, da extensão pgstattuple, e rodar REINDEX no rnd_pkey traz ele de volta para 21 MB porque a reconstrução ordena as chaves.

Tamanho não é o único custo. Com chaves crescentes, todos os inserts vão para a mesma folha mais à direita, que fica no buffer pool. Com chaves aleatórias, cada insert vai para uma folha diferente, então o índice inteiro precisa caber na memória ou os inserts começam a ler páginas do disco. A primeira alteração em cada página depois de um checkpoint também escreve uma cópia completa dessa página no WAL, então tocar muitas páginas gera muito mais WAL do que tocar poucas.

Esse é o argumento prático contra primary keys UUIDv4. O mesmo teste com um milhão de UUIDs:

CREATE TABLE u4 (id uuid PRIMARY KEY DEFAULT gen_random_uuid());
CREATE TABLE u7 (id uuid PRIMARY KEY DEFAULT uuidv7());
INSERT INTO u4 SELECT FROM generate_series(1, 1000000);
INSERT INTO u7 SELECT FROM generate_series(1, 1000000);

 index   | leaf_pages | avg_leaf_density | size
---------+------------+------------------+-------
 u4_pkey |       4778 |            72.23 | 38 MB
 u7_pkey |       3832 |            89.98 | 30 MB

O UUIDv7 coloca um timestamp em milissegundos nos bits iniciais, então os valores novos chegam quase em ordem crescente e o split da página mais à direita entra em ação. O PostgreSQL 18 já vem com uuidv7(). Se você quer UUID como chave, é esse que você deve usar. Num engine clustered como InnoDB ou SQLite a diferença é ainda maior, porque lá a chave aleatória decide onde a linha inteira vai parar.

SQLite: dois tipos de árvore

O arquivo do SQLite é uma coleção de B-trees, e a coluna rootpage da sqlite_schema diz onde cada uma começa:

CREATE TABLE users (id INTEGER PRIMARY KEY, email TEXT);
CREATE INDEX users_email ON users (email);
-- insert 100,000 rows
SELECT name, rootpage FROM sqlite_schema;

users|3
users_email|4

Nem todas são do mesmo tipo. Uma tabela é uma table B-tree: uma B+tree com chave rowid, com as linhas só nas folhas e as páginas internas guardando apenas os separadores inteiros. Um índice é uma index B-tree, que é uma B-tree clássica: as células internas guardam chaves de verdade, e cada chave aparece exatamente uma vez em algum lugar da árvore. Dá para ver a diferença com o dbstat:

SELECT name, pagetype, count(*) AS pages, sum(ncell) AS cells
FROM dbstat GROUP BY name, pagetype;

users|internal|3|728
users|leaf|729|100000
users_email|internal|8|787
users_email|leaf|788|99213

A tabela guarda as 100.000 linhas nas folhas, e as 728 células internas são cópias extras dos separadores. O índice tem 99.213 entradas nas folhas e 787 nas páginas internas, somando exatamente 100.000. Um lookup no índice pode parar numa página interna se encontrar a chave lá.

Algumas outras coisas funcionam diferente da nbtree:

• A raiz nunca muda de lugar. O rootpage fica gravado no schema, então quando a raiz enche, o balance_deeper copia o conteúdo dela para uma página filha nova e a raiz vira uma página interna acima dela. O PostgreSQL move a raiz e atualiza a metapage.
• Os splits se espalham pelas irmãs. O balance_nonroot redistribui as células entre até três páginas vizinhas em vez de sempre dividir uma página em duas, o que deixa as páginas mais cheias depois de inserts aleatórios.
• Sem links entre irmãs. As páginas do SQLite não apontam para as vizinhas. Um cursor guarda a pilha de páginas por onde desceu e volta ao pai para achar a próxima folha. O SQLite só permite um escritor por vez, então não precisa dos links à direita de Lehman e Yao para concorrência.

O que uma B-tree cobra nas escritas

Para leitura, B-tree é difícil de bater. Um lookup pontual custa um punhado fixo de leituras de página, um range scan lê folhas em ordem de chave, e os dados estão sempre totalmente ordenados, então um ORDER BY numa coluna indexada não precisa de etapa de sort.

As escritas são onde ela cobra. Alterar uma entrada de 16 bytes no índice suja uma página de 8 KB, e essa página vai acabar sendo escrita inteira de volta. Com chaves aleatórias, essas páginas sujas ficam espalhadas pelo índice todo, então as escritas viram I/O aleatório. Cada índice da tabela repete o custo: um insert numa tabela com cinco índices B-tree altera pelo menos seis páginas em lugares diferentes. Os splits somam mais, e as páginas meio vazias que eles deixam fazem o índice ficar maior que os dados.

Para a maioria dos workloads OLTP essa troca vale, já que as leituras são mais numerosas que as escritas e a parte quente do índice fica na memória. Para workloads que são quase só escrita, como logs de eventos, métricas ou filas de mensagens, outro design compensa: acumular as escritas na memória, gravá-las como arquivos ordenados numa passada sequencial e juntar esses arquivos em background. Isso é a LSM tree.

Conclusão

Uma B-tree é uma árvore de busca com nós do tamanho de uma página. O fanout alto mantém ela com três ou quatro níveis em qualquer tamanho realista, os splits mantêm toda folha na mesma profundidade, e os links entre irmãs transformam range scans em leituras sequenciais. Quase tudo que o PostgreSQL adiciona por cima, da regra de split da página mais à direita e das high keys de Lehman e Yao até a deduplicação, existe para lidar com chaves crescentes, muitos backends concorrentes e valores duplicados.

O próximo é LSM Trees: como o LevelDB e o RocksDB trocam um pouco de desempenho de leitura por escritas sempre sequenciais, e o que a compaction faz para manter as leituras sob controle.