Back to DAG

Sorted Array & Binary Search

databases

Sorted Arrays and Binary Search

Builds on to(7)
Binary Search TreeSSTableInverted IndexIVF + PQ (vector quantization)Relational Model (Codd)Join Algorithms (NLJ, Hash, Merge)Column Statistics & Histograms

A sorted array is the simplest data structure that supports efficient search. By maintaining elements in sorted order, we can use binary search to find any element in O(log n) time — far better than the O(n) linear scan required for unsorted data.

Binary search algorithm

  1. Set low = 0, high = length - 1.
  2. Compute mid = low + (high - low) / 2 (avoids integer overflow compared to (low + high) / 2).
  3. If array[mid] == target, return mid.
  4. If array[mid] < target, search the right half: low = mid + 1.
  5. If array[mid] > target, search the left half: high = mid - 1.
  6. If low > high, the element is not present.

Binary search variants

Binary search is not just about exact matches. Two critical variants are used throughout database internals:

  • Lower bound — find the first index where array[i] >= key. This is used to find the insertion point, or the start of a range query. When the exact key is not present, it returns where the key would go.

  • Upper bound — find the first index where array[i] > key. Combined with lower bound, this defines a range: all elements equal to key live in [lower_bound, upper_bound).

Insertion cost

The downside of sorted arrays is insertion: O(n). To insert a new element, you must shift all larger elements one position to the right to make room. This makes sorted arrays impractical as a mutable data structure for large datasets — but perfect for immutable, write-once structures.

Merging two sorted arrays

Given two sorted arrays of sizes n and m, they can be merged into a single sorted array in O(n + m) time using the classic merge algorithm: maintain two pointers, always take the smaller element, advance that pointer.

Where sorted arrays appear in databases

  • SSTable data blocks: each block in an SSTable (Sorted String Table) is a sorted array of key-value pairs. Lookups within a block use binary search.
  • B-tree node keys: the keys within a single B-tree node are a sorted array. The node uses binary search to route queries to the correct child.
  • Sorted runs in merge sort: external merge sort produces sorted runs that are merged — the same sorted-array merge algorithm.
  • Interpolation search: for uniformly distributed data, you can estimate the position as low + ((target - array[low]) * (high - low)) / (array[high] - array[low]), achieving expected O(log log n).

Real-Life: Binary Search in SSTable Blocks

Real-World Example

In an LSM-tree database like LevelDB or RocksDB, data is stored in SSTables — immutable files of sorted key-value pairs. Each SSTable is divided into blocks (typically 4 KB).

Reading a key from an SSTable block:

  1. The block contains a sorted array of keys with their values.
  2. The database performs binary search over the keys to find the target.
  3. If found, it returns the value. If not, it knows the key is not in this block.

Building an SSTable (flush from memtable):

  1. The memtable (a sorted in-memory structure like a skip list) is iterated in order.
  2. Keys are written sequentially into SSTable blocks — already sorted.
  3. No insertion shifting needed because the file is written once, sequentially.

Compaction (merging SSTables):

  1. Two sorted SSTables are merged into one, using the two-pointer merge algorithm.
  2. This is O(n + m) — the same merge algorithm used in merge sort.

This pattern — build sorted arrays in bulk, search with binary search, merge when needed — is the foundation of LSM-tree storage engines used in Cassandra, RocksDB, LevelDB, and ScyllaDB.

Binary Search: Finding Key 42

Binary Search for key = 42 Array: [5, 12, 18, 25, 33, 42, 51, 67, 73, 89] Step 1: low=0, high=9, mid=4 (value=33) 33 < 42, go right 5 12 18 25 33 42 51 67 73 89 Step 2: low=5, high=9, mid=7 (value=67) 67 > 42, go left 42 51 67 73 89 Step 3: low=5, high=6, mid=5 (value=42) FOUND at index 5 42 51 Merging Two Sorted Arrays A: [3, 8, 15] B: [5, 10, 12] Result: [3, 5, 8, 10, 12, 15] Two pointers advance through A and B, always picking the smaller. O(n + m) time.
Step 1 of 3