> Какая особенность B-Tree связана с физической реализацией (Go)

Короткий ответ

B-Tree в физической реализации опирается на размер страницы или блока, обычно 4 КБ или 8 КБ, чтобы один узел помещался в одну страницу диска. Это даёт высокий fanout и низкую высоту дерева, поэтому поиск требует мало дисковых I/O. В Go это проявляется при проектировании структур под page cache, mmap и выравнивание.

Подход к решению

Ключевая особенность B-Tree связана с тем, что логическая структура дерева проектируется под физическую организацию носителя. Узел дерева соответствует странице или блоку, а не произвольному объекту в heap. Поэтому fanout выбирается так, чтобы ключи и указатели помещались в страницу с учётом заголовков, выравнивания и служебных полей.

На практике это означает несколько trade-off. Больший fanout уменьшает высоту дерева и число дисковых операций, но увеличивает стоимость split и merge. Меньший fanout упрощает модификации, но повышает высоту и количество I/O. В Go нужно явно контролировать размер структур, избегать лишних указателей и учитывать, что slice и map не дают прямого контроля над layout.

Также важно различать B-Tree и B+Tree. В B+Tree внутренние узлы хранят только ключи и указатели, а данные находятся в листьях. Это увеличивает fanout внутренних узлов и улучшает последовательное сканирование. В физической реализации это часто выражается в том, что листья связаны в список, а страницы читаются последовательно.

Пример кода

GO
package main

import (
	"encoding/binary"
	"fmt"
	"unsafe"
)

const pageSize = 4096

type slot struct {
	Key   uint64
	Value uint64
}

type node struct {
	Leaf     bool
	Count    uint16
	Slots    [maxSlots]slot
	Next     uint64
	Reserved [pageSize - unsafe.Sizeof(bool(false)) - unsafe.Sizeof(uint16(0)) - unsafe.Sizeof([maxSlots]slot{}) - unsafe.Sizeof(uint64(0))]byte
}

const maxSlots = (pageSize - 8 - 2 - 8) / int(unsafe.Sizeof(slot{}))

func (n *node) insert(key, value uint64) bool {
	if int(n.Count) >= maxSlots {
		return false
	}
	n.Slots[n.Count] = slot{Key: key, Value: value}
	n.Count++
	return true
}

func (n *node) search(key uint64) (uint64, bool) {
	for i := 0; i < int(n.Count); i++ {
		if n.Slots[i].Key == key {
			return n.Slots[i].Value, true
		}
	}
	return 0, false
}

func main() {
	var n node
	n.Leaf = true
	n.insert(42, 100)
	v, ok := n.search(42)
	fmt.Println(v, ok, maxSlots, unsafe.Sizeof(n))
	_ = binary.LittleEndian
}

Edge cases

Первый edge case - размер страницы не совпадает с размером структуры из-за выравнивания. В Go компилятор может добавить padding, поэтому unsafe.Sizeof и реальный layout нужно проверять отдельно. Второй - переполнение узла при вставке, что требует split и обновления родителя. Третий - конкурентный доступ к страницам, где нужны latch, lock coupling или copy-on-write. Четвёртый - частичная запись страницы при сбое, что требует WAL или journal. Пятый - переменная длина ключей, из-за чего фиксированный массив слотов не подходит и нужен slotted page layout.

Как отвечать на собеседовании

Стоит сразу сказать, что B-Tree проектируется под страничную организацию диска или памяти. Затем объяснить связь между fanout, высотой дерева и количеством I/O. После этого привести пример на Go, где структура узла выравнивается под page size. В конце упомянуть trade-off между split, merge, конкурентностью и WAL. Если спросят про B+Tree, добавить, что данные хранятся в листьях, а внутренние узлы только направляют поиск.

Что проверяет интервьюер

Интервьюер проверяет понимание связи алгоритма с физическим уровнем хранения. Ему важно, видит ли кандидат разницу между абстрактным B-Tree и его реализацией поверх страниц. Также проверяется знание Go на уровне layout структур, выравнивания и контроля памяти. Дополнительно оценивается понимание trade-off по fanout, конкурентности, WAL и отказоустойчивости.