Binary Search Trees

Keep smaller to the left and bigger to the right, and finding a contact takes a few steps; then see why balance matters, which sorted map your language has, and how a database's B-tree finds one row in a billion.

Updated

Binary Search Trees

  1. A Contact List That's Fast to Search and Easy to Change: Binary Search Trees (Journeyman): Keep 100,000 contacts so a name is found on every keystroke, new contacts go in all day, and the screen shows everyone A to Z, or from Kai to Maya, without sorting: why an unsorted list, a sorted array and a dictionary each fall short, and the structure that fixes them, the binary search tree.
  2. The Sorted Import That Made Search Crawl: Why Balance Matters (Journeyman): Keep a contact list fast however its names arrive: see why a sorted import turns a plain binary search tree into a line as slow as a list, why shuffling and rebuilding don't fix it, and which always-balanced sorted map your language gives you.
  3. One Row in a Billion: B-Trees and Database Indexes (Freelancer): Find one customer by email among a billion rows in a few disk reads, not minutes: why reading every row and a binary search tree are both too slow on disk, and the structure inside nearly every database index, the B-tree.

Exercise: The Contact List Tree

  1. Exercise: The Contact List Tree (Journeyman): The sales team's 100,000 contacts need a find on every keystroke, adds all day, A to Z on demand, and removals: build the contact list, name each operation's growth rate, and pass a busy-day test that only a fast choice can.