The baseline every index is measured against — scan every element, or halve the range each comparison.

Ordered nodes that give O(log n) lookups when balanced — and O(n) when they are not.

The first self-balancing BST: rotations keep height logarithmic no matter the insertion order.

Balance by colouring rather than strict height, trading slightly taller trees for cheaper inserts.

Self-adjusting tree that rotates every accessed node to the root, making hot keys progressively cheaper.

Separate chaining: every slot holds a list, so collisions extend a chain instead of hunting for space.

Open addressing: every key lives in the table itself, probing forward until it finds a free slot.

Each slot is a small fixed bucket — fewer probes, better cache behaviour, and an overflow area when a bucket fills.

Keys become paths of characters, so lookup costs the length of the key rather than the size of the set.

A trie with single-child chains collapsed into one edge, cutting the node count on sparse key sets.

A trie-BST hybrid: three children per node instead of one per alphabet symbol, trading speed for memory.

Wide nodes that keep the tree shallow, splitting and promoting keys upward so every leaf stays the same depth.

The database index: all values live in linked leaves, so range scans walk sideways instead of back up the tree.