Sharding and the ubiquitous B-tree

Distributed databases with Peter Mattis

Topic 9 of 13

Published Sep 30, 2026 · Clip 52:21–55:32 (3:11)

Peter explains sharding: basic hash-based sharding with a fixed number of shards, the painful resharding problem, and consistent hashing as an improvement (as in Cassandra). CockroachDB instead partitions a contiguous key space, Bigtable/Spanner/HBase style, with an index on top of contiguous spans — which he notes is essentially a B-tree when you squint. He also explains that B-tree indexes underlie database indexes providing sorted order, citing the paper 'The Ubiquitous B-tree.'