How is a database structured internally? How does a B-tree index work?

A database typically stores data on disk in files structured for efficient access and modification. Inside, data is organized into tables, which may have indexes to speed up searches.

A B-tree (balanced tree) is a data structure used for indexes in databases. It is a tree with multiple keys in each node and several children, allowing data to be stored in sorted order and quickly find the needed records.

How a B-tree index works:

• Each node contains multiple keys and pointers to child nodes.
• All keys in the left subtree are less than the key in the node, and in the right — greater.
• When searching by index, the algorithm descends the tree, comparing the sought value with the keys in the nodes, choosing the correct path.
• The tree is balanced, so the height of the tree is minimal, ensuring logarithmic search time.

An example of a simplified B-tree structure:

// B-tree node
struct BTreeNode {
    keys     []int
    children []*BTreeNode
    leaf     bool
}

// Search for a key in B-tree
func (n *BTreeNode) Search(key int) bool {
    i := 0
    for i < len(n.keys) && key > n.keys[i] {
        i++
    }
    if i < len(n.keys) && key == n.keys[i] {
        return true
    }
    if n.leaf {
        return false
    }
    return n.children[i].Search(key)
}

Thus, a B-tree index allows quick record retrieval in the database, minimizing disk read operations.