Ordered trees and balance: the read is free, the write pays

Year 2 / Module 10 Algorithms and data structures / Unit 5 / Ordered trees and balance: the read is free, the write pays

Ordered trees and balance: the read is free, the write pays

HCI2102 · Unit 5 of 10

Every balanced tree buys a logarithmic search with extra work distributed over updates, so which tree wins is decided by the read-to-write ratio and the concurrency model rather than by the bound.

Ordered trees and balance: the read is free, the write pays

Unit four showed that a bound carries a precondition about the keys. An ordered map carries one about the writes. Search a balanced tree and the work grows with the logarithm of the number of keys, so the bound is quoted as though it chose the structure. Every balanced tree reaches the same logarithmic search, and the structures that refuse to enforce a balance invariant reach it anyway, each buying the search with extra work spread across updates. Which tree wins is therefore decided by the ratio of reads to writes and by the concurrency model, not by the bound.

The logarithmic promise is shared, so it cannot decide

Adelson-Velskii and Landis (1962) gave the founding result: an organisation of information in which search and recording both take a number of operations proportional to the logarithm of the number of elements. The bound holds whatever order the elements arrive in. The device is an invariant on shape: the heights of the two subtrees of any node differ by at most one, and a bounded number of rotations restores it after every insertion or deletion. The logarithmic read is bought with rotations on the write.

Once a logarithmic search is available, the question is what it costs to hold. The literature answers with a parameter rather than a number. Nievergelt and Reingold (1973) introduced trees of bounded balance, easy to maintain under insertions and deletions, with search time only moderately longer than in a completely balanced tree. They carry a parameter that sets the compromise between short search time and infrequent restructuring, so the read and the write are on a dial, and the dial is the design decision.

Guibas and Sedgewick (1978) showed how little the choice of dial matters to the guarantee. Red-black trees, 2-3-4 trees, AVL trees and weight-balanced trees are all colourings of a binary tree sharing one set of update operations. A family taught as unrelated algorithms therefore reduces to one analysis, and no source can rank them by the bound, because they do not differ on it; they differ in how the update absorbs the cost of keeping shape.

The parameter is set by the device, not the mathematics

Bayer and McCreight (1972) sized the ordered index to the storage device rather than to the mathematics. Their index for a file on a direct-access store is maintained in time proportional to the logarithm of the index size to a device-dependent base, chosen so the scheme becomes near optimal, with storage utilisation of at least fifty per cent and experiments on indexes up to 100,000 keys. A wide node that fills a page turns a long sequence of comparisons into one seek, and the same tree on another device would be sized wrongly.

The balance can also be achieved for a memory the algorithm cannot measure. Bender, Demaine and Farach-Colton (2000) give a cache-oblivious B-tree, a static layout with logarithmic search in a hierarchy whose block size is never given to the algorithm, extended to a dynamic version with efficient updates: one design fits its parameter to hardware it knows, the other to a hierarchy it never sees.

The invariant can be replaced by randomness

The invariant is one way to buy the bound, not the only one. Aragon and Seidel (1989) attach a random priority to each node and keep it in heap order alongside the search order, so a randomised search tree has expected logarithmic operations with no balance condition to maintain. Pugh (1990) reached the same trade with skip lists, which use probabilistic rather than strictly enforced balancing and, he reports, make insertion and deletion much simpler and faster than the equivalent balanced-tree algorithms.

Sleator and Tarjan (1985) removed the invariant entirely. A splay tree keeps all the standard search operations at an amortised logarithmic bound, and is as efficient as a static optimum tree to within a constant factor on long access sequences, its efficiency coming not from an explicit structural constraint but from restructuring on every access. The write path has become the read path: the structure pays for the promise each time it is used rather than each time it changes.

The versioned interface makes the write pay twice

When the interface keeps old versions, the update cost stops being a detail. Driscoll, Sarnak, Sleator and Tarjan (1989) give path copying and node copying, which make ordinary pointer-based structures persistent. They build persistent binary search trees with logarithmic access, insertion and deletion and constant space per insertion and deletion. A versioned editor, a snapshot read and an undo history all want exactly this, and the price is a write path that must preserve the old version rather than overwrite it.

Path copying is the mechanism. An update copies each node on the path from the root to the changed leaf and leaves every other node in place, so the untouched subtrees are shared with the previous version. One update allocates work proportional to the logarithm of the number of keys rather than to the size of the tree, and Driscoll and colleagues (1989) add node copying and fat nodes to reduce that cost further.

The trade becomes the design, and concurrency is a second axis

The clearest case is a storage engine choosing between two ordered maps that share one interface. O'Neil, Cheng, Gawlick and O'Neil (1996) motivated the log-structured merge-tree from the cost of maintaining a B-tree under a high insert rate. Maintaining the index in real time effectively doubles the transaction's I/O cost, raising total system cost by up to fifty per cent. Their structure defers and batches index changes, cascading them from a memory component through disk components, so the read consults several sorted runs instead of one balanced tree. The read-to-write ratio is no longer a fact about a workload the designer receives but a parameter the structure prices.

Once writers share the tree, the read-to-write ratio is not the only axis. Blelloch, Ferizovic and Sun (2016) reduce the ordered set to a single join over weight-balanced trees that yields union, intersection, difference and filtering. They prove the algorithms work-efficient and highly parallel across four balancing schemes, AVL trees, red-black trees, weight-balanced trees and treaps, with more than 45 times speedup on 64 cores. The finding that matters is the similarity: all four perform alike, so under a parallel join the invariant stops deciding and the concurrency model starts.

Contested question: can prediction replace the invariant?

The literature disagrees about whether the balance invariant is still the right answer for an ordered index. Kraska, Beutel, Chi, Dean and Polyzotis (2018) argue that an index is a model predicting a record's position from its key. A B-tree is one such model, and they argue it can be replaced by a learned model whose error bounds guide a local search, so the invariant becomes a special case of a predictor.

The opposing position holds that the invariant is what makes the bound independent of the data. Guibas and Sedgewick (1978) and Bayer and McCreight (1972) give structures whose logarithmic cost needs no assumption about how the keys arrive. Nievergelt and Reingold (1973) give one whose parameter is set by the designer rather than by a distribution. A learned index earns its speed by fitting a distribution it must be trained on, and an index that must answer for any key set cannot assume one, so it answers worst for the reader whose name, place or script its training data held least.

A study would settle the disagreement. It would compare a learned index with a balanced tree on a workload whose key distribution is adversarial and shifting, at a stated read-to-write ratio, and report tail latency and space under a stream of updates. That comparison partly exists. Sun, Zhou and Li (2023) evaluate the leading learned indexes against traditional ones in one framework: they win on simple distributions and read-heavy workloads and lose on complicated distributions, on range queries and under concurrent writes, with no single learned index best on every dataset. The results Kraska and colleagues reported depend on a workload shape the evaluation names. No source here reports that tail.

The sides differ in what their evidence covers. Guibas and Sedgewick (1978) and Bayer and McCreight (1972) prove bounds that hold for any order of arrival, an unconditional result, while Kraska and colleagues (2018) report initial results on the tasks they chose. The strongest objection is that an invariant fixes a shape a stable workload may never need, so a fitted model can win outright when the distribution is known. While the dispute is open, a designer keeps an assumption-free tree as the default and treats a learned index as a cache a fallback can replace.

Where the argument is heading

The named work points the same way for ordered indexes as it did for hashing. Blelloch and colleagues (2016) reduce the ordered set to one parallel join, Luo and Carey (2019) make the read-to-write trade the axis of a design space, and Kraska and colleagues (2018) put the invariant itself in question.

The sources this unit rests on

Adelson-Velskii, G. M. and Landis, E. M. (1962). An algorithm for the organisation of information. Soviet Mathematics Doklady 3, 1259-1263. https://zhjwpku.com/assets/pdf/AED2-10-avl-paper.pdf Adelson-Velskii and Landis give the first self-balancing binary search tree, in which search and recording both take time logarithmic in the number of elements whatever order the keys arrive. It buys the logarithmic read with rotations on update.
Aragon, C. and Seidel, R. (1989). Randomized search trees. 30th Annual Symposium on Foundations of Computer Science. doi:10.1109/sfcs.1989.63531 Aragon and Seidel give the treap, in which a random priority per node keeps a heap order alongside the search order, giving expected logarithmic operations without an explicit balance condition. It shows the invariant can be replaced by randomness.
Bayer, R. and McCreight, E. M. (1972). Organisation and maintenance of large ordered indexes. Acta Informatica. doi:10.1007/bf00288683 Bayer and McCreight design an index for a file on a direct-access store, with retrieval, insertion and deletion proportional to the logarithm of the index size to a device-dependent base, storage utilisation of at least fifty per cent. Its parameter is a property of the hardware.
Bender, M., Demaine, E. and Farach-Colton, M. (2000). Cache-oblivious B-trees. IEEE Symposium on Foundations of Computer Science (FOCS). doi:10.1109/sfcs.2000.892128 Bender, Demaine and Farach-Colton give a cache-oblivious B-tree, a static layout with logarithmic search in a hierarchy whose block size is never given to the algorithm, extended to a dynamic version. It is the unit's contrast case.
Blelloch, G. E., Ferizovic, D. and Sun, Y. (2016). Just Join for Parallel Ordered Sets. Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures. doi:10.1145/2935764.2935768 Blelloch, Ferizovic and Sun reduce the ordered set to a single join over weight-balanced trees, deriving union, intersection, difference and filtering, and prove the algorithms work-efficient across four balancing schemes, with more than 45 times speedup on 64 cores. It is a construction with measurements.
Driscoll, J. R., Sarnak, N., Sleator, D. D. and Tarjan, R. E. (1989). Making data structures persistent. Journal of Computer and System Sciences. doi:10.1016/0022-0000(89)90034-2 Driscoll, Sarnak, Sleator and Tarjan give path copying, fat nodes and node copying, which make ordinary pointer-based structures persistent, and build persistent binary search trees with logarithmic access and constant space per update, making the versioned interface a cost on the write. It is a construction with a proof.
Guibas, L. J. and Sedgewick, R. (1978). A dichromatic framework for balanced trees. 19th Annual Symposium on Foundations of Computer Science (sfcs 1978). doi:10.1109/sfcs.1978.3 Guibas and Sedgewick describe red-black trees, 2-3-4 trees, AVL trees and weight-balanced trees as colourings of a binary tree sharing one set of update operations. It is why no source can rank these trees by the bound.
Kraska, T., Beutel, A., Chi, E. H., Dean, J. and Polyzotis, N. (2018). The Case for Learned Index Structures. Proceedings of the 2018 International Conference on Management of Data. doi:10.1145/3183713.3196909 Kraska and colleagues argue that an index is a model predicting a record's position from its key, replace the B-tree with a learned model whose error bounds guide a local search, and report substantial advantages in initial results on a distribution a general index cannot assume.
Luo, C. and Carey, M. J. (2019). LSM-based storage techniques: a survey. The VLDB Journal. doi:10.1007/s00778-019-00555-y Luo and Carey survey LSM-based storage, systematising memtables, compaction policies, level organisation and key-value separation, and reporting the read, write and space trade each choice makes, with read amplification among the open problems. It is where the trade still bites.
Nievergelt, J. and Reingold, E. M. (1973). Binary Search Trees of Bounded Balance. SIAM Journal on Computing. doi:10.1137/0202005 Nievergelt and Reingold introduce trees of bounded balance, easy to maintain under insertions and deletions, with search time only moderately longer than in a completely balanced tree, carrying a parameter that sets the compromise. It shows the invariant itself is a design choice.
O'Neil, P., Cheng, E., Gawlick, D. and O'Neil, E. (1996). The log-structured merge-tree (LSM-tree). Acta Informatica. doi:10.1007/s002360050048 O'Neil, Cheng, Gawlick and O'Neil introduce the LSM-tree, motivated by maintaining a B-tree under a high insert rate, where real-time index maintenance doubles the transaction's I/O cost. It defers and batches index changes, making the read-to-write ratio a priced parameter.
Pugh, W. (1990). Skip lists: a probabilistic alternative to balanced trees. Communications of the ACM. doi:10.1145/78973.78977 Pugh gives skip lists, which use probabilistic rather than strictly enforced balancing, and reports that insertion and deletion are much simpler and faster than the equivalent algorithms for balanced trees. The structure shipped in databases.
Sleator, D. D. and Tarjan, R. E. (1985). Self-adjusting binary search trees. Journal of the ACM. doi:10.1145/3828.3835 Sleator and Tarjan give the splay tree, whose operations have an amortised logarithmic bound, and prove it as efficient as a static optimum tree to within a constant factor, It is the measure the unit's contested question tests.
Sun, Z., Zhou, X. and Li, G. (2023). Learned Index: A Comprehensive Experimental Evaluation. Proceedings of the VLDB Endowment. doi:10.14778/3594512.3594528 Sun, Zhou and Li compare state-of-the-art learned indexes with traditional ones under one framework across key lookup, insert, concurrency and bulk loading, finding them ahead on simple distributions and read-heavy workloads and behind on complex distributions, range queries and writes. It is the comparison the unit asked for.

Check your understanding & apply it · 4 questions, 1 essay

1The unit sharpens the usual claim about balanced trees into a specific thesis. Which option states that thesis?

2A team moves an in-memory B-tree index from a machine with 4 KB pages to one with 512-byte pages and keeps each node's capacity at the same number of keys. Which prediction does the unit support?

3The contested section sets two positions against each other and then names what would settle the disagreement. Which option states the positions and the settling evidence correctly?

4The unit reports the read-write trade as the sources make it. Which option reports that comparison correctly?

5Essay Choose one ordered index whose workload is not read-dominated, for example an append-only event store, a versioned document editor that keeps undo history, a write-heavy key-value store, or an in-memory ordered map on a machine with many writer threads. State the read-to-write ratio and who writes concurrently, then argue whether a balance invariant is the right structure for that workload. Name the structure you would choose and the guarantee it gives, say where the work of keeping shape lands, and set out the measurement that would tell a designer whether the choice was right. Use Adelson-Velskii and Landis (1962), Nievergelt and Reingold (1973) or Guibas and Sedgewick (1978) for the invariant and its parameter; use Bayer and McCreight (1972) or Bender and colleagues (2000) if the structure is sized to a device; use Pugh (1990) or Sleator and Tarjan (1985) if you replace the invariant; use Driscoll and colleagues (1989) if the interface is versioned; use O'Neil and colleagues (1996) or Luo and Carey (2019) for a write-optimised store; and use Blelloch and colleagues (2016) for a concurrent workload or Kraska and colleagues (2018) for prediction.

Begin by naming the workload rather than the structure, which is the whole point of the unit: give the ratio of reads to writes and say who writes concurrently, because two interfaces that both expose an ordered map require different guarantees once those numbers differ. For an append-only event store that is read rarely and written constantly, the read-to-write ratio is very low, and the unit's evidence points away from a comparison-balanced tree: O'Neil and colleagues (1996) show that maintaining a B-tree index in real time effectively doubles the transaction's I/O cost and raises total system cost by up to fifty per cent, and their log-structured merge-tree instead defers and batches index changes across sorted runs, which is the same choice a modern store makes with the read amplification Luo and Carey (2019) catalogue. If the interface is versioned, as an editor with undo history is, the write pays again, and Driscoll and colleagues (1989) give the persistent forms that keep logarithmic access and constant space per update, so the argument must price the old version the write must preserve. If the tree must instead answer for any key set with the bound independent of the data, the invariant is the right answer: Adelson-Velskii and Landis (1962) buy the logarithmic read with rotations on update, Nievergelt and Reingold (1973) put the read against the write on an explicit parameter, and Guibas and Sedgewick (1978) show the schemes share one analysis, so the choice is the dial rather than the bound. Where the bound must hold for a memory the structure cannot measure, Bender and colleagues (2000) give the cache-oblivious layout, and where the invariant is replaced, Pugh (1990) or Sleator and Tarjan (1985) give probabilistic and self-adjusting alternatives. If many threads write, the concurrency model enters: Blelloch and colleagues (2016) reduce the ordered set to one parallel join and find four balancing schemes performing similarly, so the invariant stops deciding. Close by naming the measurement: report the read-to-write ratio actually observed, the tail latency of both reads and writes rather than the mean, and, if a learned model is proposed, the same tail under a shifting key distribution, since that is what would separate Kraska and colleagues (2018) from the invariant.