The buddy system manages a memory pool of size 2K as a binary tree of power-of-two blocks. To satisfy a request of R bytes it picks the smallest order o with 2o ≥ R, then repeatedly halves the smallest available larger block until a block of exactly that order exists:
split(block, order):
while block.order > order:
left, right = halve(block) // two "buddies"
freeList[block.order-1] += right
block = left
return mark_allocated(block)
Freeing reverses the process. Two buddies — blocks of the same order whose start addresses differ by exactly one bit, buddy = start XOR 2^order — coalesce back into their parent the moment both are free, which is what keeps the pool from fragmenting into unusable slivers:
free(block):
mark_free(block)
b = buddy_of(block)
while b exists and b.free and b.order == block.order:
block = merge(block, b)
b = buddy_of(block)
- Memory map (top strip) — the pool laid out linearly, left to right by address; click any allocated segment to select it.
- Split/merge tree (main view) — the same pool as the full binary buddy tree: a solid bar is a currently-existing block; a dashed outline means that region has been split further, and you can trace both halves below it. Drag to pan, scroll/pinch to zoom.
- Internal fragmentation — the gap between what you asked for and the power-of-two block you actually got (e.g. a 20 KB request inside a 32 KB block wastes 12 KB) — the structural cost of the buddy system's O(log N) split/merge speed.
Real-world relevance: this is the exact allocator behind the Linux kernel's page allocator (mm/page_alloc.c) and early Unix/BSD kmem allocators — fast, simple, and still in every machine you own.