Keep a changing collection in order so that searching it, inserting into it and scanning a range of it all stay fast, and recognise the same structure underneath a database index, a file system and a priority queue

Keeping Things in Order

Halving the search, then keeping the halving possible while the data changes. Trees, balance, ranges and the sort that gets you there.

8 lessons, written and corrected before you arrived. Reading them here needs no account. The first reads the whole way through; the others open and then stop, because a page nobody owns cannot tell who is reading it. Starting the course gives you your own copy, where every idea has problems standing under it and you can ask about any sentence.

Start reading

This is course 3 of 8 in a reading track: tell in advance which approach survives a million rows. The track is an order, not a gate, and the rest of it is on one page.

01Halving the SearchOrder lets a search throw away half the collection at every step, which turns a million comparisons into twenty. The whole course is about keeping that possible while the data changes.
02A Sorted List You Can Changeopening onlyWrite the halving down as a tree of comparisons and the structure becomes the search. Insertions then cost one walk down and one link, with nothing shifted along to make room.
03When a Tree Degenerates Into a Listopening onlyThe shape of a search tree is decided by the order items arrive in, and the most ordinary arrival order of all, already sorted, turns it into a chain with no halving left.
04Keeping It Balancedopening onlyA tree can be kept shallow by one small move: when a node leans too far, lift its heavier side into its place. Checking and repairing on the way back up costs almost nothing.
05Asking for Everything Betweenopening onlyEverything between two dates, the next one along, the ten largest. These are the questions hashing could not touch, and an ordered tree answers all of them from the shape it already has.
06Wide Trees and the Diskopening onlyOn a disk, reading one item and reading a thousand cost the same. That single fact reshapes the tree into something wide and shallow, which is the index inside every database.
07Always Knowing the Smallestopening onlySome collections are never searched. They are asked for their smallest item, over and over, and a structure that promises only that is simpler and faster than one that promises order.
08Putting It in Order in the First Placeopening onlyMerging two ordered runs is easy, so split the collection until the pieces are trivially ordered and merge back up. That costs n log n, and no comparison sort can beat it.