# Making unwinding through JIT-ed code scalable - The b-tree

DevFeed: [Making unwinding through JIT-ed code scalable - The b-tree](<https://devfeed.tech/articles/making-unwinding-through-jit-ed-code-scalable-the-b-tree-25076.md>)

Original publisher: [Read original article](<https://databasearchitects.blogspot.com/2022/06/btree.html>)

Author: Thomas Neumann (noreply@blogger.com)

Published: 2022-06-26T08:56:00Z

Content type: article

Language: en

Sources: [Database Architects](<https://devfeed.tech/sources/database-architects.md>)

Topics: [Data structures](<https://devfeed.tech/topics/data-structures.md>), [Concurrency](<https://devfeed.tech/topics/concurrency.md>), [Concurrent Programming](<https://devfeed.tech/topics/concurrent-programming.md>), [Code](<https://devfeed.tech/topics/code.md>)

Tags: [code](<https://devfeed.tech/tags/code.md>), [data-structure](<https://devfeed.tech/tags/data-structure.md>), [implementation](<https://devfeed.tech/tags/implementation.md>), [memory](<https://devfeed.tech/tags/memory.md>), [node](<https://devfeed.tech/tags/node.md>), [object](<https://devfeed.tech/tags/object.md>), [recursion](<https://devfeed.tech/tags/recursion.md>), [structure](<https://devfeed.tech/tags/structure.md>), [synchronization](<https://devfeed.tech/tags/synchronization.md>)

## AI overview

This article explains the data-structure and infrastructure portions of a scalable unwinding system that uses a B-tree for fast lookup and data locality. It describes node organization, invariants, fence keys, helper functions, optimistic lock coupling, memory reclamation through a free list, and recursive destruction; insert, remove, and lookup operations are deferred to the next article.

## Source excerpt

This article is part of the series about scalable unwinding that starts here. We use a b-tree because it offers fast lookup, good data locality, and a scalable implementation is reasonable easy when using optimistic lock coupling. Nevertheless a b-tree is a non-trivial data structure. To avoid having one huge article that includes all details of the b-tree, we just discuss the data structure themselves and some helper functions here, the insert/remove/lookup operations will be discussed in the next article. A b-tree partitions its elements by value. An inner node contains a sorted list of separator/child pairs, with the guarantee that the elements in the sub-tree rooted at the child pointer will be <= the separator. The leaf nodes contains sorted lists of (base, size, object) entries, where the object is responsible for unwinding entries between base and base+size. An b-tree maintains the invariants that 1) all nodes except the root are at least half full, and 2) a leaf nodes have the same distance to the root. This guarantees us logarithmic lookup costs. Note that we use fence-keys, i.e., the inner nodes have a separator for the right-most entries, too, which is not the case in all b-tree implementations: // The largest possible separator value static const uintptr_t max_separator = ~((uintptr_t) (0)); // Inner entry. The child tree contains all entries <= separator struct inner_entry { uintptr_t separator; struct btree_node *child; }; // Leaf entry. Stores an object entry struct leaf_entry { uintptr_t base, size; struct object *ob; }; // node types enum node_type { btree_node_inner, btree_node_leaf, btree_node_free }; // Node sizes. Chosen such that the result size is roughly 256 bytes #define max_fanout_inner 15 #define max_fanout_leaf 10 // A btree node struct btree_node { // The version lock used for optimistic lock coupling struct version_lock version_lock; // The number of entries unsigned entry_count; // The type enum node_type type; // The payload union { /