Packed Memory Array

A Packed Memory Array (PMA)—also known in classical database theory as a sequential file maintenance data structure—is a dynamic, self-rebalancing array data structure in computation and algorithms introduced by American computer scientist Dan E. Willard between 1982 and 1992 and formulated for the cache-oblivious model by Michael A. Bender, Erik D. Demaine, and Martin Farach-Colton in 2000. A Packed Memory Array maintains a dynamic set of N ordered elements inside a single contiguous memory array A[0 .. M − 1] of physical capacity M = Θ(N) by interleaving the N occupied elements with M − N empty slots (gaps) governed by a hierarchy of depth-dependent density thresholds.

In a conventional densely packed sorted array of length N, binary search locates an element in O(log N) comparisons and sequential range scans traverse K contiguous elements in optimal O(1 + K / B) cache-line or disk-block transfers (where B is the block size), but inserting or deleting a single element forces an O(N) memory shift. Conversely, pointer-based balanced search trees such as red–black trees, AVL trees, splay trees, treaps, and skip lists support insertions and deletions in O(log N) pointer updates, but scatter tree nodes across non-contiguous heap addresses so that scanning K consecutive keys in sorted order incurs up to O(K) random cache misses. Even classic B-trees store elements contiguously only within individual leaf pages of fixed size B, requiring pointers to jump between logically adjacent leaf pages unless the leaves themselves are maintained in physical address order. The Packed Memory Array resolves this tension: all N elements reside in sorted physical order inside a single contiguous array A of size M ≤ c · N (typically c ∈ [2, 4]), enabling hardware-prefetched sequential scans at O(1 + K / B) memory transfers while reducing arbitrary insertions and deletions from O(N) to O(log² N) amortized (and de-amortized worst-case) element moves—corresponding to O(1 + (log² N) / B) block transfers in the cache-oblivious memory hierarchy.

Contiguous Locality versus Update Shifting Costs

Consider maintaining an ordered sequence of N records x₁ < x₂ < … < x_N inside an array A[0 .. M − 1] of M slots, where each slot holds either one valid element or a null marker (∅) indicating an empty gap, subject to the order invariant that if 0 ≤ i < j < M and both A[i] ≠ ∅ and A[j] ≠ ∅, then A[i] < A[j].

This abstraction models three foundational problems in systems and algorithm design:

1. Sequential File Maintenance in Storage Engines: Maintaining database records sorted by primary key across contiguous disk or NVMe extents so that range queries stream sequentially without random seeks.
2. Cache-Oblivious Search Trees and B-Trees: Maintaining the leaves of a cache-oblivious B-tree without knowing the L1, L2, L3 cache-line or page size B at compile time.
3. List Labeling and Order Maintenance: Assigning integer labels from {1, 2, …, M} to N dynamic list elements with M = O(N) so that order queries reduce to integer comparisons on the assigned array indices.

While Andrew C. Yao and Paul F. Dietz showed that in polynomial-size label spaces M = N^1+ε insertions require only O(log N) relabelings, restricting the array to linear space M = O(N)—so that a constant fraction of the array is always occupied—induces a matching information-theoretic lower bound of Ω(log² N) element moves per insertion, proved for deterministic algorithms by Dietz, Seiferas, and Zhang (1994) and for randomized algorithms by Bulánek, Koucký, and Saks (2012).

Hierarchical Calibration Tree Over Array Segments

To achieve the optimal O(log² N) bound, a Packed Memory Array overlays an implicit complete binary calibration tree T on top of the contiguous physical array A[0 .. M − 1]:

1. Leaf Segments (Windows): Partition the array A of power-of-two capacity M into L = M / S contiguous leaf segments of size S = Θ(log N) slots each. Leaf k ∈ {0, 1, …, L − 1} corresponds to the slice A[k · S .. (k + 1)S − 1].
2. Internal Calibration Nodes: Above the L leaf segments sits a conceptual complete binary tree T of height H = log₂ L = log₂(M / S) = log₂ N − O(log log N). A node u at depth d ∈ {0, 1, …, H} (with root at depth d = 0 and leaves at depth d = H) corresponds to a contiguous subarray A_u of capacity cap(u) = M / 2^d = S · 2^H−d.
3. Implicit Indexing (Zero Tree Pointers): Because T is a complete binary tree over power-of-two slices, the calibration tree requires zero pointer storage: the subarray bounds [l(u), r(u)] of the depth-d ancestor containing index i are computed in O(1) bitwise operations via l(u) = i & ~(cap(u) − 1) and r(u) = l(u) + cap(u) − 1.

For any node u ∈ T, let count(u) denote the number of occupied slots inside subarray A_u, and define the density of node u as δ(u) = count(u) / cap(u) ∈ [0, 1].

Upper and Lower Density Envelopes (τ_d and ρ_d)

If every node u ∈ T enforced the exact same maximum density threshold τ = 3/4, then inserting one element into a leaf segment of density 3/4 would overflow both the leaf and any ancestor already at density 3/4, cascading to the root on consecutive insertions and degrading amortized performance to O(N).

Willard (1982) and Bender, Demaine, and Farach-Colton (2000) prevented cascading overflows by assigning stricter density bounds to shallower nodes and looser bounds to deeper nodes. Choose four constants satisfying 0 < ρ_H < ρ₀ < τ₀ < τ_H < 1, such as ρ_H = 1/4, ρ₀ = 1/2, τ₀ = 3/4, and τ_H = 1. For every depth d ∈ {0, 1, …, H}, the upper density threshold τ_d and lower density threshold ρ_d are interpolated linearly with depth d:

Between any parent at depth d − 1 and its children at depth d, both thresholds relax by a step of size Θ(1 / H) = Θ(1 / log N):

A node u at depth d is within threshold (in balance) if and only if ρ_d ≤ δ(u) ≤ τ_d.

The Rebalance-and-Redistribute Sweep

To insert a new element x (or delete an existing element x) inside leaf segment u_H:

1. Local Leaf Update (O(S) = O(log N) moves): If inserting x into leaf u_H keeps δ(u_H) ≤ τ_H, shift elements within the S-slot leaf window in O(S) = O(log N) moves and terminate.
2. Upward Walk to Find the Lowest Balanced Ancestor: If the update causes leaf u_H to violate [ρ_H, τ_H], walk up the ancestor chain u_H, u_H−1, …, u_d until finding the lowest ancestor u_d at depth d whose updated density still satisfies ρ_d ≤ δ(u_d) ≤ τ_d (or rebuild A at capacity 2M or M/2 if the root u₀ is out of bounds).
3. Even Redistribution Across Subarray A_ud (O(cap(u_d)) moves): Collect all count(u_d) occupied elements inside A_ud and redistribute them evenly across the cap(u_d) slots of A_ud so every descendant leaf segment receives count(u_d) / 2^H−d elements. This two-pass in-place pack-and-spread sweep executes in O(cap(u_d)) time and O(1 + cap(u_d) / B) sequential block transfers.

Proof of O(log² N) Amortized Element Moves

Suppose an insertion triggers a rebalance at ancestor u_d at depth d because one of its children v ∈ {v_L, v_R} at depth d + 1 exceeded τ_d+1. Because u_d is within threshold at depth d, its density satisfies δ(u_d) ≤ τ_d = τ_d+1 − Δτ. Evenly redistributing A_ud resets the density of both children v_L and v_R at depth d + 1 to δ(v) = δ(u_d) ≤ τ_d.

Before child v at depth d + 1 can overflow its upper threshold τ_d+1 = τ_d + Δτ again (and force another rebalance at u_d), at least Δτ · cap(v) additional insertions must occur inside A_v:

Charging the O(cap(u_d)) element moves of the rebalance at u_d across those Ω(cap(u_d) / log N) updates charges O(log N) amortized moves to each update at depth d. Summing across all H + 1 = O(log N) depth levels along the root-to-leaf path yields O(log² N) amortized element moves and O(1 + (log² N) / B) amortized cache-oblivious block transfers per insertion or deletion.

Willard's De-Amortized Worst-Case O(log² N) Bound

While subtree redistribution achieves O(log² N) amortized time, a single rebalance near the root takes O(N) work in that step. Dan E. Willard (1982, 1986, 1992) proved that the Packed Memory Array can be de-amortized to guarantee O(log² N) element moves in the strict worst case on every individual insertion and deletion by running incremental anticipatory migration schedules of O(log N) shifts per level whenever a child enters a warning density band.

Cache-Oblivious B-Trees and Adaptive PMAs

To reduce point-search memory transfers from O(log N) to the optimal B-tree bound of O(log_B N) without knowing B, Bender, Demaine, and Farach-Colton (2000, 2005) paired a bottom Packed Memory Array of L = Θ(N / log N) leaf segments with a static top index tree laid out in recursive van Emde Boas memory layout (splitting the tree at half-height √L so every subtree of height h sits in 2^h contiguous slots). Point searches take O(log_B N) transfers, range scans take O(1 + K / B) transfers, and updates take O(log_B N + (log² N) / B) amortized transfers across all cache levels simultaneously.

Furthermore, Michael A. Bender and Haodong Hu (2007) introduced the Adaptive Packed Memory Array (APMA), which tracks hammered leaf segments receiving repeated insertions and biases subtree redistributions to leave extra empty space in active regions—improving sequential and append-heavy insertions from Θ(log² N) to O(log N) amortized element moves while preserving the O(log² N) worst-case bound.

Dynamic Compressed Sparse Row (PCSR) Graph Storage

In high-performance graph algorithms such as breadth-first search, depth-first search, and Dijkstra's algorithm, static graphs G = (V, E) are stored in Compressed Sparse Row (CSR) format: a vertex offset array *offsets*[0 .. n] pointing into a contiguous edge array *edges*[0 .. 2m − 1]. Standard CSR maximizes sequential scan bandwidth, but inserting a single edge requires O(m) time to shift the edges array. Brian Wheatman and Helen Xu (2018) introduced Packed Compressed Sparse Row (PCSR), replacing the static edges array with a Packed Memory Array ordered by (u, v) to support dynamic edge insertions and deletions in O(log² m) moves while running parallel graph traversals at 70%–95% of static CSR speed.

How does binary search work on a Packed Memory Array when empty gaps are interleaved with elements?

Binary search skips empty slots in O(1) work per probe using either: (1) Sentinel key duplication, where each empty slot stores a copy of the nearest preceding valid key alongside a 1-bit occupancy bitmap so binary search compares keys directly at any index A[mid]; or (2) Leaf-level compaction, where elements inside each leaf segment of size S = Θ(log N) are packed at the front of the segment with a header recording the segment's minimum key and occupancy count.

Why is the leaf segment size chosen as Θ(log N) rather than 1 slot?

At a single-slot leaf (S = 1), the density δ(u) can only take discrete values 0 or 1, making fractional threshold steps Δτ = Θ(1 / log N) impossible near the bottom of the tree. Setting the leaf capacity to S = Θ(log N) ensures that inserting one element changes the leaf's density by 1 / S = O(1 / log N) ≤ Δτ, keeping the linear threshold schedule τ_d well-separated down to depth H.

Can a Packed Memory Array outperform a B⁺-tree in an in-memory database?

For range-scan analytical workloads and streaming graph analytics, a Packed Memory Array often outperforms a pointer-based B⁺-tree by 2×–5× on range queries because all leaf segments are physically contiguous in virtual memory, enabling hardware stride prefetchers and SIMD scans without chasing leaf pointers.

Is the Ω(log² N) lower bound breakable using randomization?

No. Jan Bulánek, Michal Koucký, and Michael Saks (2012) proved that even randomized online array maintenance algorithms must perform Ω(log² N) expected element moves per insertion when maintaining N ordered items in an array of linear size M = O(N).

1. Willard, D. E. (1992). "A density control algorithm for doing insertions and deletions in a sequentially ordered file in a good worst-case time."90014-7) Information and Computation, 97(2), 150–204.
2. Bender, M. A., Demaine, E. D., & Farach-Colton, M. (2005). "Cache-oblivious B-trees." SIAM Journal on Computing, 35(2), 341–358.
3. Bender, M. A., & Hu, H. (2007). "An adaptive packed-memory array." ACM Transactions on Database Systems, 32(4), Article 26, 1–43.
4. Bulánek, J., Koucký, M., & Saks, M. (2012). "Tight lower bounds for the online labeling problem." In Proceedings of the 44th Annual ACM Symposium on Theory of Computing (STOC 2012) (pp. 1185–1198).
5. Wheatman, B., & Xu, H. (2018). "Packed Compressed Sparse Row: A dynamic graph representation." In 2018 IEEE High Performance Extreme Computing Conference (HPEC) (pp. 1–7).