Geometric Search Trees

Randomized set data structures eschew self-balancing logic for simpler, probabilistic item organization. When deriving the necessary randomness via pseudorandom functions of the stored items themselves, the resulting graphs depend on the stored set only, but not the order of insertions and deletions. This history-independence ensures that no information about previously deleted items can be reconstructed (Naor & Teague, 2001), and it enables efficient set fingerprinting (Pugh & Teitelbaum, 1989) when using the data structure as a merkle-tree (Merkle, 1989).

For these reasons, randomized search trees and related data structures have been studied for decades. The most prominent such data structures are treaps (Seidel & Aragon, 1996), skip-lists (Pugh, 1990), and, more recently, zip-trees (Tarjan et al., 2021). All three are different takes on approximating the distribution of items in perfectly balanced binary search trees.

While binary trees are highly efficient in theory, they are less efficient on actual hardware than trees that store more than one item per vertex. Unfortunately, generalizing binary randomized data structures to higher-arity counterparts has proven more difficult than in the case of deterministically self-balancing trees. Providing a simple such generalization is the impetus for our work. Figure 1 plots lookup performance of a zip-tree versus a 32-ary tree of ours; our tree is roughly twice as fast (note the logarithmic y-axis). On secondary storage, we can expect the performance difference to be even more pronounced.

We present the geometric search trees (G-trees), a family of randomized search trees that provides a unified perspective on several independently researched data structures, including zip-trees, zip-zip-trees (Gila et al., 2023), skip-trees (Messeguer, 1997), dense skip-trees (Spiegel & Reynolds Jr, 2009), merkle-search-trees (Auvolat & Taïani, 2019), and prolly-trees (Boodman et al., 2016). Our framework allows us to trivially define efficient trees that store a bounded number of items per vertex. These trees are arguably the first such randomized search trees whose conceptual complexity is just as low as that of their binary counterparts.

Our key insight is to take a byproduct of the usual definition of zip-trees, turn it into a defining property of its own, and to then generalize it. Zip-trees assign geometrically chosen ranks to their items, and use these ranks for probabilistic balancing. A consequence of their balancing mechanism is that certain sequences of items with colliding ranks form sorted linked lists. It turns out we can view and even define zip-trees as collections of such linked lists.

From this definition, which is based on arranging sorted linked lists in a certain fashion, it is only a small step to arranging arbitrary set data structures in the same fashion. This yields our G-trees, a family of trees that is parameterized over a secondary search data structure. Using simple linked lists as the underlying data structure yields the zip-trees. Recursively instantiating the G-trees with other G-trees yields a natural (and efficient) generalization of the zip-zip-trees. And finally, using linked lists of $k$ items per vertex yields a generalization of the zip-trees where each node can store up to $k$ items.

The G-trees not only define a unique tree shape for any set of items with associated ranks, they also offer a unified means of implementation. We provide generalizations of the zipping and unzipping algorithms of the original zip-trees, and use them to implement insertion and deletion. These general algorithms can be applied to all G-trees whose underlying set data structure supports splitting at arbitrary keys and joining two non-overlapping sets. The algorithms perform a number of splits or joins proportional to the number of distinct ranks in the tree, which is logarithmic in the total number of items with high probability.

We give an overview of related work in Section 2, before introducing preliminary definitions and notation in Section 3. We present the geometric trees in Section 4, including a thorough analysis and a an overview of old and novel G-trees. Section 5 describes efficient algorithms for mutating G-trees.

The practically-minded reader can safely skip ahead to Section 3, whereas the more academically inclined may wish to stick around for Section 2, where we outline the current state of the art and contextualize our contributions.Data structures whose exact shape is determined solely by their contents and not by the order of insertion and deletion operations have been studied for decades. This property has been given several names, such as unique representation (Snyder, 1977), structural unicity (Auvolat & Taïani, 2019), confluent persistence (Driscoll et al., 1994), and anti-persistence or history-independence (Naor & Teague, 2001). Deterministically self-balancing history-independent set data structures necessarily take super-logarithmic time to update under arbitrary insertions and deletions (Snyder, 1977). Hence, several probabilistic history-independent data structures have been devised which support membership queries and update operations in logarithmic time with high probability.

Well-known such (pseuso-) randomized set data structures include hash tries (as presented, for example, by Pugh and Teitelbaum (Pugh & Teitelbaum, 1989)), treaps (Seidel & Aragon, 1996), and skip-lists (Pugh, 1990). More recently, zip-trees  (Tarjan et al., 2021) and zip-zip-trees  (Gila et al., 2023) have been proposed as more efficient variants of skip-lists.

All these data structures approximate the vertex distribution of binary balanced search trees. While binary search trees are theoretically efficient, CPU caches or block-sized reads from secondary storage make it so that trees that store more than a single item per vertex outperform binary trees in practice. Theoretical models to capture this behavior in the analysis of algorithms and data structures include external memory models (Aggarwal & Vitter, 1988) and cache-oblivious models (Frigo et al., 1999).

Several attempts have been made to find randomized data structures that perform well in an external memory model. Golovin (Golovin, 2009) has proposed bushy treaps (B-treaps) to approximate the behavior of B-trees via treaps. Unfortunately, B-treaps are complicated enough that even their author recommends using simpler alternatives such as the B-skip-list (Golovin, 2010). The B-skip-list still involves a tuning parameter beyond the probability distribution for assigning node levels, a nontrivial invariant, and virtual memory management via hash tables rather than simple usage of pointers. In short, the conceptual complexity goes far beyond that of binary skip-lists or treaps.

Safavi and Seybold (Safavi & Seybold, 2023) propose randomized-block-search-trees (RBSTs) as another generalization of binary treaps that performs well in an external-memory model. The construction involves multiple tuning parameters, two distinct layers of data structure internals, and a highly nontrivial complexity analysis.

Bender et al (Bender et al., 2016) first specify a history-independent packed-memory array (PMA), and then build a history-independent B-tree analogon and an external-memory skip-list on top of the PMA. So there is again a two-layered aproach; the PMA introduces a significant chunk of conceptual complexity that is not part of regular treaps or skip-lists.

Some proponents of randomized data structures claim that a significant advantage over self-balancing data structures is their greater simplicity (Pugh, 1990; Seidel & Aragon, 1996). It seems safe to say that none of the external-memory constructions we have just listed retain this advantage.

All prior work that does achieve sufficient simplicity buys it at the price of vertices that must store a dynamic, unbounded number of items. The skip-trees (Messeguer, 1997) are the first such data structure, effectively converting a skip-list into a tree: each vertex stores sequences of items that are being skipped-over together in the corresponding skip-list. The relatively unknown dense skip-trees (Spiegel & Reynolds Jr, 2009) provide two optimizations: expected node size can be increased by flipping coins of success probabilities $\frac{1}{k}\text{,}$ and empty vertices are eliminated from the tree. The merkle-search-trees (MSTs) (Auvolat & Taïani, 2019) independently reinvent skip-trees with flexible probabilities similar to dense skip-trees, but without the compression of empty vertices. Additionally, prolly-trees  (Boodman et al., 2016) provide a slightly different take, where a rolling hash function over the keys/values is used to determine the set of items in each node, rather than via explicit split and join operations.

None of these data structures can provide a non-probabilistic upper bound on the number of items per vertex. This hampers efficient implementation; and adversarial data suppliers can trivially produce $n$ items in $\mathcal{O}(n)$ expected time that must all be stored in the same vertex.

Here, we define fundamental terminology, and provide proper definitions and background for zip-trees.

3.1 Data Structures

3.2 Pseudorandom Geometric Distributions

3.3 Zip-Trees

We can now give a formal definition of zip trees (Tarjan et al., 2021). Let ${\mathrm{rank}}_{\frac{1}{2}}$ be a rank function. The zip tree of some set $S$ is the unique search tree whose set of items is $S$, and which is a heap when ordering by rank first, item second. Equivalently, it must be a heap with respect to ranks such that left children always have strictly lesser rank than their parents. Figure 2 gives an example.The example tree is taken from a stackoverflow answer, the interested reader can find there a detailed description of the isomorphism to skip-lists for that same example tree.

We derive our G-trees by generalizing zip trees. To do so, we start with a non-standard definition of zip trees:

This recursive definition reveals an interesting property of zip trees: colliding ranks. From this definition, it is easy to see that the items of maximal rank form a linked list of right children at the root of the zip-tree. The same holds recursively in all subtrees as well. We can characterize these linked lists of items of equal rank as a sequence $Q=q_0\prec q_1\prec \dots q_k$ of items colliding in a superset $S\supseteq Q$ if all item in $Q$ have equal rank, and there is no $s\in S$ of greater rank such that $q_0\prec s\prec q_k\text{.}$ Figure 3 visualizes the linked lists formed by maximal sets of colliding items in a zip tree.

We can even define zip trees in terms of maximal colliding item sequences, by using all items of maximal rank as partition items in a single construction step:

Figure 4 vizualizes this perspective on zip trees. Note how the linked-list pointers are exactly the pointers between items of equal rank, whereas both left and right child pointers always involve a strict decrease in rank. In that sense, the list-based definition fixes an asymmetry of the original definition, which only requires strictly decreasing ranks for left children.

From this non-standard characterization of zip-trees, there is a natural generalization: rather than representing maximal sequences of colliding items (and the items’ left subtrees) with sorted linked lists, we can represent them with arbitrary set data structures:

This generalization turns out to be remarkably powerful. We can express several well-known data structures as G-trees (Section 4.2), we find novel, cache-efficient data structures amongst the G-trees (Section 4.3), and we can derive efficient implementation techniques for all of them (Section 5).

We can regard any G-tree from two perspectives. First, as a high-level tree of maximal colliding sequences. We refer to the nodes of this conceptual tree as G-nodes. The height of this tree is equal to the number of distinct ranks of the underlying set, which is in $\mathcal{O}(\log (n))$ with high probability (we give an analysis in Section 4.1). Figure 5 visualizes our running example from this perspective.

And second, given a specific set data structure $\mathfrak{S}$, we can study the resulting in-memory graphs with pointers as edges. If $\mathfrak{S}$ is the type of sorted linked lists, for example, these concrete graphs are isomorphic to the zip trees (compare Figure 4, which we can interpret as depicting a G-tree using sorted linked lists).

When we select the rank of each item as a pseudorandom function of the item itself, a tree of G-nodes is uniquely determined by the set of its items. Hence, if $\mathfrak{S}$ is history-independent, so is the G-tree.

When interpreted as trees of G-nodes, the G-trees are exactly the dense skip-trees of Spiegel and Reynolds Jr (Spiegel & Reynolds Jr, 2009). Spiegel and Reynolds Jr never consider the internal structure of the G-nodes, however, thus missing the instantiations that we discuss later.

4.1 Analysis

4.2 Well-Known G-Trees

4.3 Novel G-Trees

Having shown that the G-trees encompass several useful and well-known data structures, we now give some members of the family that have not been independently described before. In particular, we tackle the problem of finding history-independent data structures that are efficient on secondary storage (or in terms of cpu caches) by storing up to $k$ items in a single vertex. Previous solutions (Bender et al., 2016; Golovin, 2009, 2010; Safavi & Seybold, 2023) all incur a significant overhead in terms of conceptual complexity compared to their binary counterparts. With G-trees, we merely need to change the underlying set datastructure $\mathfrak{S}$ to one that stores items in blocks of $k$.

A key intuition behind classic zip trees is that of choosing ranks from a geometric distribution with $p=1-\frac{1}{2}=\frac{1}{2}$ because this is the distribution of the height of a randomly chosen vertex in a perfectly balanced binary tree. For $k$-ary trees, the same intuition instructs us to draw ranks from a geometric distribution with $p=1-\frac{1}{k}\text{,}$ as this is the distribution of heights in a perfectly balanced $k$-ary tree. Our analysis confirmes that — with high probability — the resulting trees are of logarithmic height and their G-nodes store $\mathcal{O}(k)$ items.

The second key insight toward an efficient $k$-ary data structure is, paradoxically, that there is no need to be clever about it. Sorted linked lists are naïve, inefficient data structures, yet zip trees are efficient. We can be similarly naïve for our $k$-ary construction.

We use a sorted linked list in which every node stores up to $k$ items. We require all items to be stored as early in the list as possible; this is the simplemost way of achieving history-independence. In other words, the only node to store fewer than $k$ items is the final node. We call such a list a $k$-list (see Figure 9).

Instantiating G-trees with the $k$-lists and a geometric distribution of $p=1-\frac{1}{1+k}$ yields a family of data structures we call the $k$-zip-trees. Figure 10 depicts the $2$-zip-tree for our running example set.

The $k$-lists are inefficient data structures — inserting or deleting the first item requires $\mathcal{O}(n)$ time in a $k$-list of $n$ items. The $k$-zip-trees are nevertheless efficient, because the expected size of the G-nodes, and hence, the expected length of the $k$-lists, is constant for any $p$. More efficient alternatives to $k$-lists exist, such as unrolled linked lists (Shao et al., 1994). These are not history-independent, however.

What is the expected height of a $k$-zip-tree? Asymptotically, we know it to be in $\mathcal{O}(\log n)$, since we have G-nodes of $\mathcal{O}(\log n)$ different ranks, each a list of $\mathcal{O}(k)$ items (which has a length in $\mathcal{O}(k)$). Figure 11 gives experimental measures for some specific $n$ and $k$. The height amplification we report is the height of each tree divided by the height of a perfectly-balanced $k+1$-ary tree on $n$ vertices.

Tree Height

	$n=100$	$n=1,000$	$n=10,000$	$n=100,000$
$k=1$	15.29 (5.61)	26.59 (8.89)	38.20 (9.47)	50.58 (11.86)
$k=3$	8.61 (2.40)	14.92 (3.38)	21.97 (4.41)	29.13 (4.93)
$k=15$	4.28 (0.98)	8.06 (2.04)	12.36 (2.43)	16.66 (2.45)
$k=63$	2.37 (0.24)	5.05 (1.43)	8.43 (1.69)	12.08 (2.52)

Height Amplification

	$n=100$	$n=1,000$	$n=10,000$	$n=100,000$
$k=1$	2.18 (0.11)	2.66 (0.09)	2.73 (0.05)	2.98 (0.04)
$k=3$	2.15 (0.15)	2.98 (0.14)	3.14 (0.09)	3.24 (0.06)
$k=15$	2.14 (0.24)	2.69 (0.23)	3.09 (0.15)	3.33 (0.10)
$k=63$	1.18 (0.06)	2.53 (0.36)	2.81 (0.19)	4.03 (0.28)

Another concern of interest is space amplification: in the worst case, every item would be in its own $k$-list, resulting in a space amplification factor of $k$. Intuitively, this occurs only rarely, however: the expected size of each G-node is $k$, and the probability for a G-node to have size $s<k$ decreases exponentially in $k-s$. Any overfull G-node consists of one or more full linked-list vertices, plus exactly one underfull linked-list vertex. Hence, the overfull G-nodes contribute an amplification factor of at most two. Roughly half of the nodes will be overful, so we can expect a space amplification around $1.5$. Figure 12 backs up this intuition with experimental data.

Space Amplification

	$n=100$	$n=1,000$	$n=10,000$	$n=100,000$
$k=1$	1 (0)	1 (0)	1 (0)	1 (0)
$k=3$	1.338 (0.0055)	1.302 (0.0006)	1.298 (0.0000)	1.297 (0.0000)
$k=15$	1.743 (0.0786)	1.544 (0.0061)	1.515 (0.0006)	1.512 (0.0000)
$k=63$	2.431 (0.612)	1.669 (0.0316)	1.578 (0.0032)	1.565 (0.0003)

Recursive instantiation of G-trees with other G-trees leads to the family of ${\text{zip}}^k$-trees when using linked lists (i.e., $1$-lists) as the recursion anchor. We can similarly use arbitrary $k$-lists as the recursion anchor to obtain the $k$-zip-trees, the $k$-zip-zip-trees, and so on.

Through some small adjustments, the definition of G-trees can be adapted to yield generalizations of skip-lists and history-independent analogons of B⁺-trees (Comer, 1979). We sketch these extensions in Appendix B.

We now present asymptotically efficient algorithms for working with G-trees. To optimize for clarity of presentation, we describe purely functional algorithms: all functions return new values rather than mutating their inputs.

We explicitly distinguish between non-empty and possibly-empty G-trees and internal set data structures, to clarify which cases can arise in our algorithms. To reinforce those distinctions, our pseudocode comes with pseudotypes. The typing also aids in keeping straight the multiple levels of parametric polymorphism (“generics”). Finally, pseudotypes allow us to explicitly define the functions that must be available on $\mathfrak{S}$ for our algorithms to work.

The functions we require of a NonemptySet are standard functions that are easily implemented in $\mathcal{O}(\log (n))$ time with typical set data structures33Not that we needed an efficient implementation: since G-nodes have constant expected size, even $\mathcal{O}(n)$ implementations do not hurt the asymptotic efficiency of our algorithms.. The only choice worth commenting on is that of using a specialized insert_min function instead of a generic insert function. This choice is to allow for more efficient, specialized implementations, as well as to highlight that our algorithms interact with the internal set data structures in a surprisingly constrained manner.

Before giving our main algorithms, we define some helper functions:

While it is possible to derive insertion and deletion algorithms by generalizing the original zip tree algorithms (see Appendix C for examples), we opt for a fully self-contained presentation here. Zipping and unzipping are similar to the join and split functions of join-based tree algorithms (Blelloch et al., 2016). We consistently use zip and unzip terminology when operating on G-trees, and join and split terminology when operating on the underlying set datastructure $\mathfrak{S}$.

We build our insertion and deletion algorithms from algorithms for unzipping and zipping G-trees. Unzipping takes a key and splits a G-tree into the tree of all items less than the key and the tree of all items greater than the keyThe key itself occurs in neither returned tree, even if it is part of the input tree.. Zipping takes two trees, the first containing only items strictly lesser than any item of the second, and joins them together into a single tree. We call this version of zipping zip2, because it takes two arguments. We also use a zip3 function, which additionally incorporates a single item into the tree that is strictly greater than all items of the first tree, and strictly less than all items of the second tree. Insertion and deletion can then be implemented as composition of unzipping and zipping (zip3 and zip2, respectively) — see Figure 13.

To unzip a G-tree, split the inner set of the root GTreeNode, and then performs a case distinctionWe give a more thorough description in the form of code comments. to determine whether it is necessary to recurse:

Since the expected size of G-nodes is constant with high probability, we can treat all functions of the NonemptySet interface as running in constant time. Each recursive call of the unzip function is to a GTreeNode of strictly decreasing rank, so the recursion depth is bounded by the height of the G-tree, which is logarithmic with high probability. Hence, the overall running time is in $\mathcal{O}(\log (n))$ with high probability.

We can similarly give a recursive algorithmAgain, the main description takes the form of code comments. for zipping together two G-trees with the same complexity properties:

To implement zipping of two G-trees with an additional item in between them, we can simply convert that item into a singleton G-tree, and then call zip2 twice:

With unzip, zip2, and zip3 in place, insertion and deletion in expected logarithmic time become trivial:

We want to emphasize that our choice of algorithms optimizes for elegance, not for (non-asymptotic) efficiency. Implementations based on in-place mutations will outperform our immutable algorithms. A direct implementation of zip3 will outperform the reduction to two applications of zip2. Iterative implementations might outperform recursive implementations. And finally, direct implementations of insertion and deletion should outperform those based off unzipping and zipping the full trees. The original zip-tree paper (Tarjan et al., 2021) contains examples of direct algorithms that zip and unzip only parts of a tree; our algorithms can be adapted to work analogously, and we provide variants for G-trees in Appendix C.

We have generalized the zip trees to the rich family of G-trees. G-trees must be instantiated with a concrete set data structure; using a linked list yields the zip trees, and direct recursive self-instantiation yields the zip-zip-trees. All G-trees are history-independent if the underlying set data structure is history-independent, and admit the same efficient algorithms for mutating them. We have proven the G-trees to be similar to perfectly balanced search trees with high probability, a property that makes them asymptotically and practically efficient.

Beyond merely generalizing existing data structures, we have defined the $k$-zip-trees, a conceptually simple family of history-independent data structures that store up to $k$ items in a single vertex. Such data structures make more efficient use of hardware caches than binary trees, allowing the $k$-zip-trees to outperform the binary zip trees.

We have published the code powering our experiments on github (under the MIT license). The implementation written is in rust, and can be built with the cargo package manager. Run cargo run --bin stats to replicate the experiments for Figure 6, Figure 7, Figure 8, Figure 11, and Figure 12. Run cargo bench to recreate the benchmark for Figure 1.

We now sketch several variants of G-trees that might be useful in practice. Highlights include a G-tree-analogon of the B⁺-tree (Comer, 1979), and a cache-efficient generalization of the skip-list.

When search trees store not only keys but key-value pairs, some usecases benefit from storing all key-value pairs in leaves of the tree. To support efficient lookup of the leaves, the inner vertices of the tree store duplicates of certain keys. We can easily adapt G-trees to this behavior by placing items not only in the tree layer corresponding to their rank but also on all lower layers. Figure 14 depicts such a naïve leafy G-tree, and Figure 15 and Figure 16 show concrete instantiations with a 1-list (a naïve leafy zip-tree) and a 2-list (a naïve leafy 2-zip-tree) respectively. We arbitrarily44Spoiler: the ordering is arbitrary in principle, but our choice will surface a deep connection to skip-lists in a few paragraphs. choose to sort items of lower rank to the right of their copies of higher rank.

The figures clearly show a deficiency of this naïve approach: almost all items have a single pointer to the layer below, except for the first item of each rank, which needs two pointers. We can restore uniformity by adding a dummy element $\perp$ at the start of each layer. Figure 17 gives an example of the resulting (proper) leafy G-tree; Figure 18 shows a leafy zip-tree, and Figure 19 shows a leafy 2-zip-tree.

The reader familiar with skip-lists should immediately see that Figure 18 — the rendering of a leafy zip-tree — essentially shows a skip-list, except that some of the edges within the same layer are missing. Figure 21 shows a proper skip-list with the same items and ranks for comparison. Characterizing the “missing” edges from the perspective of leafy G-trees is trivial: there are no edges between vertices of equal rank that belong to different G-nodes.

Characterizing the missing edges from the perspective of skip-lists is quite instructive. Consider the algorithm for searching in a skip-list: start in the topmost layer, follow pointers within a layer until overshooting the search target, drop down a layer when you would overshoot. The “missing” edges are exactly the edges that are always guaranteed to overshoot — if they did not overshoot, the search would never have descended into this part of the skip-list in the first place. Search in a leafy zip-tree encounters a null pointer at the end of each G-node, whereas search in a skip-list blindly dereferences a pointer and performs a comparison whose result is already predetermined.

As far as we are aware, this observation of two classes of next-pointers in skip-lists — those that always overshoot in a search, and those which might not overshoot in some searches — is novel. The fact that skip-lists get to conflate the two classes and algorithmically handle them in a uniform way might well be the underlying reason why skip-lists are so appealing compared to binary search trees.

We can easily augment the leafy G-trees to generalize the skip-lists by adding pointers between successive G-nodes of equal rank. Figure 20 shows the resulting linked leafy G-tree for our running example. Figure 21 instantiates with a linked list, obtaining a linked leafy zip-tree, i.e., a skip-list. Figure 22 shows the instantiation with a 2-list, yielding a linked leafy 2-zip-tree. Instantiating the linked leafy zip-trees with $k$-lists gives a family of generalizations of skip-lists that store $k$ items per vertex. Finding such a family could easily be reason for a dedicated publication, were it not for the fact that the powerful framework of geometric trees gives us this family essentially for free.

To conclude, we point out that linking only the leaves of a leafy G-tree yields a family analogous to the B⁺-trees (Comer, 1979). Figure 23 shows such a G⁺-tree; Figure 24 shows an instantiation with a linked list (a zip⁺-tree), and Figure 25 shows an instantiation with a 2-list (a 2-zip⁺-tree).

As alluded to in Section 5, it is possible to derive direct insertion and deletion functions for G-trees that are analgous to Algorithm 1 from the original zip tree paper. For completeness, we provide pseudocode for purely functional variants of these functions for G-trees. The functions leverage the previously defined zip2 and various helper functions.

We also define an additional helper function which joins a possibly empty Set with a greater NonemptySet.:

The following explicit delete pseudocode follows a very similar structure to Algorithm 1 from  (Tarjan et al., 2021), though we use pattern matching here for consistency.