Trees, Heaps & Advanced Data Structures

Master binary trees, BSTs, balanced trees (AVL, Red-Black), heaps, priority queues, tries, and advanced structures like skip lists and Bloom filters. These are the data structures that power databases, caches, and search engines. PostgreSQL indexes are B+ trees. When you run add_index :users, :email, you are creating a B+ tree that enables O(log n) lookups instead of O(n) sequential scans. Understanding tree balancing explains why index maintenance has a cost on writes. Nested set pattern (acts_as_nested_set) stores hierarchical data as a tree using left/right values for O(1) subtree queries. Closure table pattern (closure_tree gem) uses an adjacency list with materialized paths. Priority queues appear in Sidekiq's job scheduling (which job runs next?) and in Rails' own middleware stack ordering. Tries power autocompletion in search boxes — if you have ever built a search-as-you-type feature, understanding tries makes you build it better.