AlgoPlus//databases / b-tree
Read the theory

B-Tree Index

Keys stay sorted in a shallow, balanced tree — so a lookup is a few hops, not a full scan.

Phase
Full scan
Keys indexed
0
Comparisons
—
Your insert sequence
Legend
Active node / key
Index comparisons
Full-scan comparisons
AI Tutor Workspace
—
In a nutshell
A B-tree is the balanced, shallow tree most databases use for indexes. Each node holds a sorted run of keys, so a lookup walks from the root down a few child pointers instead of scanning every row. When a node overflows it splits and pushes its middle key up, keeping the tree balanced and only a few levels deep — O(log n) lookups.
Ready
Press play to begin the cinematic walkthrough.
Keep keys sorted in a shallow, wide tree so lookups follow a few child pointers instead of scanning every row. Splits push medians upward to keep it balanced.
Key terms
Go deeper in the lesson
Read the full theory, intuition & complexity for B-Tree Index.
Code Simulator
▼
1
def bst(root, val):
2
    # insert / search / traverse
3
    if root is None:
4
        return Node(val)  # Inserted/Found
5
    if val < root.val:
6
        root.left = bst(root.left, val)
7
    else:
8
        root.right = bst(root.right, val)
9
    # traversal order
10
    visit(root.val)  # Visit
Why Python? · Readable first, fast second

Dynamically typed and interpreted — every comparison and swap is dispatched by the interpreter at run time, so tight loops run roughly 10–100× slower than compiled C/C++. Unbeatable for learning the idea with the least code; not what you reach for when the inner loop is the bottleneck.