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

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

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

Author: Thomas Neumann (noreply@blogger.com)

Published: 2022-06-26T09:00:00Z

Content type: article

Language: en

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

Topics: [Algorithms](<https://devfeed.tech/topics/algorithms.md>), [Code](<https://devfeed.tech/topics/code.md>), [Programming](<https://devfeed.tech/topics/programming.md>), [JIT](<https://devfeed.tech/topics/jit.md>)

Tags: [algorithms](<https://devfeed.tech/tags/algorithms.md>), [article](<https://devfeed.tech/tags/article.md>), [code](<https://devfeed.tech/tags/code.md>), [complexity](<https://devfeed.tech/tags/complexity.md>), [jit](<https://devfeed.tech/tags/jit.md>), [locking](<https://devfeed.tech/tags/locking.md>)

## AI overview

This article explains high-level B-tree insertion and deletion algorithms in a series about scalable unwinding through JIT-ed code. It describes eager splitting of full nodes during insertion to simplify top-to-bottom locking, and merging or balancing nodes during deletion to preserve occupancy and avoid upward propagation.

## Source excerpt

This article is part of the series about scalable unwinding that starts here. Now that we have all infrastructure in place, we look at the high-level algorithms. For inserts, we walk down the tree until we hit the leaf-node that should contain the new value. If that node is full, we split the leaf node, and insert a new separator into the parent node to distinguish the two nodes. To avoid propagating that split further up (as the inner node might be full, too, requiring an inner split), we eagerly split full inner nodes when walking down. This guarantees that the parent of a node is never full, which allows us to look at nodes purely from top-to-bottom, which greatly simplifies locking. The splits themselves are relatively simple, we just copy the right half of each node into a new node, reduce the size of the original node, and insert a separator into the parent. However two problems require some care 1) we might have to split the root, which does not have a parent itself, and 2) the node split could mean that the value we try to insert could be either in the left or the right node. The split functions always update the node iterator to the correct node, and release the lock on the node that is not needed after the split. // Insert a new separator after splitting static void btree_node_update_separator_after_split (struct btree_node *n, uintptr_t old_separator, uintptr_t new_separator, struct btree_node *new_right) { unsigned slot = btree_node_find_inner_slot (n, old_separator); for (unsigned index = n->entry_count; index > slot; --index) n->content.children[index] = n->content.children[index - 1]; n->content.children[slot].separator = new_separator; n->content.children[slot + 1].child = new_right; n->entry_count++; } // Check if we are splitting the root static void btree_handle_root_split (struct btree *t, struct btree_node **node, struct btree_node **parent) { // We want to keep the root pointer stable to allow for contention // free reads. Thus, we split the ro