Partitioning

Range Routing

Range routing compares keys against ordered boundaries.

highlighted = computed this step

Range routing uses boundaries

A range scheme compares the key against ordered half-open boundaries. A key equal to a boundary does not go left; it continues to the next range. Note: every comparison row is produced by the compiler.

range comparison trace\text{range comparison trace}

Comparison trace

The compiled routing table contains 5 routes. The boundary-equal key uses 2 comparisons and lands at partition index 2.

routes=5,checks=2\text{routes}=5,\quad \text{checks}=2

Range and hash sharding are exact routing functions on tiny pinned key sets; real sharding adds consistent hashing, skew, hot partitions, and rebalancing cost, which are empirical and operational concerns beyond this model - no product claims.

Range routing - range:10,20keypartitiontrace9P09< 10: yes10P110< 10: no; 10< 20: yes19P119< 10: no; 19< 20: yes20P220< 10: no; 20< 20: no31P231< 10: no; 31< 20: no

Summary

Range routing is deterministic ordered comparison. Note: the book models named boundaries, not empirical load estimates.

half open ranges\text{half open ranges}