Skip to content
The Data EngineeringThe Data EngineeringBeta
About
Main content

Paying for the mismatch between arrival and access order

Data arrives in one order and is queried in another. Parcels are scanned in time order, but customers search by tracking ID. That mismatch has to be reconciled. The reconciliation has a fixed total cost that nobody escapes. You only choose when to pay it and in which currency:

  • A B-tree pays at write time. It places every key in its sorted position the moment it arrives.
  • An pays later, in the background.
  • A hash table refuses to sort at all. It pays in space and in the permanent loss of range queries.
  • A perfect hash refuses to accept new keys. It therefore pays almost nothing.

We call this idea the :