
B-trees, STL map, and Swiss tables in Go

Distributed databases with Peter Mattis
Topic 6 of 13
Published Sep 30, 2026 · Clip 30:05–39:07 (9:02)
Peter discusses his fascination with data structures and algorithms, then the story of a colleague noticing the C++ STL map (a balanced binary tree) showing up in memory profiles on Google's Gaia system. Peter implemented a B-tree version of the STL map with better spatial locality and smaller size, though sacrificing pointer stability on inserts. He explains B-trees simply — sorted arrays of ~8 items per node, splitting and recursing upward. He then tells how he implemented Swiss tables in Go: inspired by Google's Swiss office research, he noodled on beating the highly optimized Go runtime map, had a breakthrough on a flight to Bangalore, and with help from the Go issue tracker and runtime team, Go eventually shipped a Swiss-table-based map.