code an atomic C++ B++ tree that limits public heap allocations
- User
code an atomic C++ B++ tree that limits public heap allocations
Assistant
Okay, let's design and implement an atomic B+ tree in C++ with a focus on limiting public heap allocations during its operations.
Key Concepts & Strategy:
-
B+ Tree Structure:
- High-degree nodes to reduce tree height.
- Internal nodes store keys and pointers to children.
- Leaf nodes store keys and associated values (or key-value pairs).
- Leaf nodes are linked sequentially for efficient range scans.
- All leaves are at the same depth.
-
Atomicity:
- We'll use a single
std::mutexto protect the entire tree structure during operations. This makes operations likeinsert,remove,findappear atomic from the outside – they either complete successfully or have no effect. This is the simplest approach to guarantee atomicity, although it limits concurrency. Fine-grained locking (per-node) is significantly more complex.
- We'll use a single
-
Limited Heap Allocations:
- The core idea is to avoid calling
newordeletedirectly within the public methods (insert,remove,find). - We'll implement a Node Pool (memory pool) strategy.
- The
BPlusTreeclass will own a container (e.g.,std::vectororstd::list) that holds all theNodeobjects allocated during the tree's lifetime. - We'll maintain a free list (e.g.,
std::stackorstd::list) of available nodes from the pool. allocate_node()will take a node from the free list or allocate a new one from the pool if necessary (potentially pre-allocating a chunk).deallocate_node()will return a node to the free list instead of letting it be destroyed immediately.- This centralizes node management and avoids scattering small allocations. The main allocation happens when the pool is initialized or grows, not per-operation.
- The core idea is to avoid calling
Implementation Details:
- Node Size: We'll use
std::arraywithin nodes for keys and children/values for efficiency, sized according to the tree'sorder. - Templating: The tree will be templated on Key (
K) and Value (V) types, and a Comparator (Compare). - Memory Pool:
std::vector<std::unique_ptr<Node>>will own the actual node memory.std::stack<Node*>will manage the free list. - Order: A parameter
T(often denoted asMor2T) defining the maximum number of children. Max keys =T-1. Min keys =ceil(T/2) - 1. We'll usemax_childrenas the parameter.
#include <iostream> #include <vector> #include <array> #include <memory> #include <mutex> #include <stack> #include <list> #include <optional> #include <algorithm> #include <functional> // For std::less #include <cmath> // For std::ceil #include <stdexcept> // For std::runtime_error #include <utility> // For std::move, std::pair // Forward declaration template <typename K, typename V, typename Compare = std::less<K>> class BPlusTree; namespace BPlusTreeInternal { // Structure for Nodes template <typename K, typename V> struct Node { bool is_leaf = false; std::vector<K> keys; std::vector<V> values; // Only used in leaf nodes std::vector<Node<K, V>*> children; Node<K, V>* parent = nullptr; Node<K, V>* next_leaf = nullptr; // Pointer to the next leaf node // Constructor for internal nodes Node(int max_children_per_node) : keys(max_children_per_node - 1), children(max_children_per_node), is_leaf(false) {} // Constructor for leaf nodes Node(int max_children_per_node, bool is_leaf_node) : keys(max_children_per_node - 1), values(max_children_per_node - 1), // Max values = max keys children(max_children_per_node), // conceptually, though only used for leaf link is_leaf(is_leaf_node) {} // Helper to check if node is full bool is_full(int max_keys) const { // keys.size() is max capacity, keys.size() - count_elements is remaining capacity // Or simpler: check actual number of elements stored return keys.size() == max_keys; // Assuming keys vector is sized correctly initially } // Helper to check if node is underflowing (minimum elements) bool is_underflowing(int min_keys) const { return keys.size() < min_keys; } // Get number of elements currently stored size_t element_count() const { return keys.size(); } // Find index of first key >= search_key // Returns keys.size() if all keys are less than search_key size_t find_key_index(const K& search_key, const BPlusTreeInternal::Compare<K>& comp) const { // Use std::lower_bound which is efficient on sorted ranges auto it = std::lower_bound(keys.begin(), keys.end(), search_key, comp); return std::distance(keys.begin(), it); } }; // Define Compare alias inside the namespace for convenience template <typename K> using Compare = typename std::conditional< std::is_same<typename std::remove_cv<K>::type, typename std::remove_reference<K>::type>::value, std::less<K>, std::less<typename std::remove_cv<K>::type> // Handle potential const/ref keys >::type; } // namespace BPlusTreeInternal template <typename K, typename V, typename Compare = BPlusTreeInternal::Compare<K>> class BPlusTree { private: using Node = BPlusTreeInternal::Node<K, V>; using Compare = Compare; // Alias for the comparator // Maximum number of children per node int max_children; // Maximum number of keys per node = max_children - 1 int max_keys; // Minimum number of keys per node (except root) = ceil(max_children / 2) - 1 int min_keys; Node* root = nullptr; Node* first_leaf = nullptr; // Pointer to the very first leaf node // --- Memory Pool --- // Owns the memory for all nodes std::vector<std::unique_ptr<Node>> node_storage; // Tracks available nodes for reuse std::stack<Node*> free_list; // Keep track of max nodes for potential pre-allocation or limit size_t max_nodes_reserved; // Example: reserve space initially // --- Concurrency --- std::mutex tree_mutex; // --- Node Pool Methods --- Node* allocate_node(bool is_leaf = false) { std::lock_guard<std::mutex> lock(tree_mutex); // Lock pool access too Node* newNodePtr = nullptr; if (!free_list.empty()) { newNodePtr = free_list.top(); free_list.pop(); // Reset node state if needed (or ensure constructors handle it) newNodePtr->keys.clear(); newNodePtr->values.clear(); newNodePtr->children.clear(); newNodePtr->parent = nullptr; newNodePtr->next_leaf = nullptr; // Re-initialize based on is_leaf flag if necessary (constructor does this) if (is_leaf) { // Ensure it's marked as leaf and has appropriate vectors sized newNodePtr->is_leaf = true; // Resize might be expensive if not done carefully. Assume constructors are used. } else { newNodePtr->is_leaf = false; } } else { // Allocate a new node from the main storage try { // Allocate based on whether it's intended to be a leaf or internal node auto node_ptr = std::make_unique<Node>(max_children, is_leaf); newNodePtr = node_ptr.get(); node_storage.push_back(std::move(node_ptr)); // Optional: Could pre-allocate node_storage up to max_nodes_reserved } catch (const std::bad_alloc&) { // Handle allocation failure - maybe throw or return nullptr throw std::runtime_error("BPlusTree: Failed to allocate node."); } } return newNodePtr; } // IMPORTANT: This doesn't destroy the node, just returns it to the pool void deallocate_node(Node* node) { if (!node) return; std::lock_guard<std::mutex> lock(tree_mutex); // Resetting state before adding to free list is good practice node->keys.clear(); node->values.clear(); node->children.clear(); node->parent = nullptr; node->next_leaf = nullptr; node->is_leaf = false; // Default state free_list.push(node); } // Helper to get the minimum number of keys required for a node (except root) int get_min_keys() const { // Minimum elements is ceil(M/2), minimum keys = minimum elements - 1 return static_cast<int>(std::ceil(static_cast<double>(max_children) / 2.0)) -1; } // --- Core Tree Logic Methods --- // Finds the leaf node where the key should reside or be inserted. Node* find_leaf(const K& key) { std::lock_guard<std::mutex> lock(tree_mutex); // Lock for traversal if (!root) { return nullptr; } Node* current = root; while (!current->is_leaf) { // Find the first child whose key is >= search key size_t index = current->find_key_index(key, Compare()); current = current->children[index]; } return current; } // Helper to split a child node that has overflowed void split_child(Node* parent, int child_index) { Node* child_to_split = parent->children[child_index]; int num_child_keys = child_to_split->element_count(); // Create a new node (sibling) // Use the node pool via allocate_node Node* new_sibling = allocate_node(child_to_split->is_leaf); // Calculate split point: middle key index for internal node, middle element index for leaf // For max_keys = M-1, we need to move (M-1)/2 keys approx. int split_idx = (num_child_keys) / 2; // Index of the element to promote/move K middle_key = child_to_split->keys[split_idx]; // Move keys/values from the right half of child_to_split to new_sibling for (size_t i = split_idx + 1; i < num_child_keys; ++i) { new_sibling->keys.push_back(child_to_split->keys[i]); } // Clear keys from the original node beyond the split point child_to_split->keys.resize(split_idx); if (child_to_split->is_leaf) { // Move values as well for (size_t i = split_idx + 1; i < num_child_keys; ++i) { new_sibling->values.push_back(child_to_split->values[i]); } // Clear values from the original node child_to_split->values.resize(split_idx); // Update leaf linked list new_sibling->next_leaf = child_to_split->next_leaf; child_to_split->next_leaf = new_sibling; if (new_sibling->next_leaf == nullptr) { // If we split the last leaf // This case shouldn't happen if first_leaf is maintained correctly } } else { // Move children pointers for (size_t i = split_idx + 1; i < child_to_split->children.size(); ++i) { // children.size() is max_children new_sibling->children[i - (split_idx + 1)] = child_to_split->children[i]; if (child_to_split->children[i]) { child_to_split->children[i]->parent = new_sibling; } } // Clear children pointers from the original node // Set size, clear pointers beyond split point child_to_split->children.resize(split_idx + 1); // Keep pointer at split_idx // Null out pointers in the new sibling that are beyond its actual content for(size_t i = new_sibling->keys.size() + 1; i < new_sibling->children.size(); ++i) { new_sibling->children[i] = nullptr; } } // Insert the middle key and the new sibling pointer into the parent // Shift keys and children in the parent to make space parent->keys.insert(parent->keys.begin() + child_index, middle_key); parent->children.insert(parent->children.begin() + child_index + 1, new_sibling); new_sibling->parent = parent; // Clear potentially unused slots in parent's children vector if needed (optional) // parent->children might need resizing depending on vector usage. If pre-sized, clear trailing pointers. } // Handles inserting a key/value into a node, splitting if necessary void insert_into_node(Node* node, const K& key, const V& value) { Compare comp; size_t index = node->find_key_index(key, comp); // Insert key and value into the correct position node->keys.insert(node->keys.begin() + index, key); if (node->is_leaf) { node->values.insert(node->values.begin() + index, value); } // Check for overflow if (node->element_count() > max_keys) { // Node overflow - need to split Node* parent = node->parent; if (!parent) { // Root node overflowed - create new root Node* new_root = allocate_node(false); // New root is internal new_root->children.push_back(node); new_root->parent = nullptr; // Root has no parent node->parent = new_root; root = new_root; split_child(new_root, 0); // Split the old root (now child 0 of new root) // The key promoted by split_child is now in new_root->keys[0] } else { // Find index of the node within its parent's children int child_idx = -1; for(size_t i = 0; i < parent->children.size(); ++i) { if (parent->children[i] == node) { child_idx = static_cast<int>(i); break; } } if (child_idx != -1) { split_child(parent, child_idx); } else { // Should not happen throw std::runtime_error("BPlusTree internal error: parent/child relationship broken."); } } } } public: // Constructor explicit BPlusTree(int order = 100) : max_children(order) { if (order < 3) { throw std::invalid_argument("BPlusTree order must be at least 3."); } max_keys = max_children - 1; min_keys = get_min_keys(); max_nodes_reserved = 1024; // Initial reservation, adjust as needed // Optionally pre-allocate some nodes // reserve_nodes(max_nodes_reserved); // Implement reserve_nodes if desired } // Destructor ~BPlusTree() { // The node_storage vector with unique_ptrs will automatically clean up all nodes. // The free_list contains raw pointers, but they point to objects managed by node_storage. // No explicit delete calls needed here due to unique_ptr. } // Disable copy/move semantics for simplicity, as managing the pool across copies is complex. BPlusTree(const BPlusTree&) = delete; BPlusTree& operator=(const BPlusTree&) = delete; BPlusTree(BPlusTree&&) = delete; BPlusTree& operator=(BPlusTree&&) = delete; // Insert a key-value pair void insert(const K& key, const V& value) { std::lock_guard<std::mutex> lock(tree_mutex); // Lock the entire operation if (!root) { // Tree is empty, create root node (which is also a leaf) try { root = allocate_node(true); // Allocate as leaf first_leaf = root; root->keys.push_back(key); root->values.push_back(value); } catch (const std::runtime_error& e) { std::cerr << "Allocation failed: " << e.what() << std::endl; // Handle appropriately - maybe clear root if partially created? root = nullptr; first_leaf = nullptr; // Rethrow or handle error throw; } return; } // Find the appropriate leaf node Node* leaf = find_leaf(key); // find_leaf already locks/unlocks internally for traversal // Check if key already exists (optional: update or ignore) Compare comp; size_t index = leaf->find_key_index(key, comp); if (index < leaf->element_count() && !comp(key, leaf->keys[index]) && !comp(leaf->keys[index], key)) { // Key exists, update value (or handle as error/ignore) leaf->values[index] = value; return; // Operation finished } // Insert into the leaf node, potentially triggering splits up the tree insert_into_node(leaf, key, value); } // Find a value by key std::optional<V> find(const K& key) { std::lock_guard<std::mutex> lock(tree_mutex); // Lock for the entire read operation if (!root) { return std::nullopt; } Node* current = root; while (!current->is_leaf) { size_t index = current->find_key_index(key, Compare()); current = current->children[index]; if (!current) { // Should not happen in a correct B+ tree return std::nullopt; } } // Now current is the leaf node size_t index = current->find_key_index(key, Compare()); if (index < current->element_count() && !Compare()(key, current->keys[index]) && !Compare()(current->keys[index], key)) { // Key found return current->values[index]; } // Key not found return std::nullopt; } // Get the first leaf node (for iteration) Node* get_first_leaf() { std::lock_guard<std::mutex> lock(tree_mutex); return first_leaf; } // Get root (for debugging/inspection) - use with caution regarding locking Node* get_root() { // No lock here - caller must acquire tree_mutex if needed return root; } // Get node pool storage (for debugging/inspection) - use with caution regarding locking const std::vector<std::unique_ptr<Node>>& get_node_storage() const { // No lock here - caller must acquire tree_mutex if needed return node_storage; } // Simple print function for debugging (uses locks internally) void print() { std::lock_guard<std::mutex> lock(tree_mutex); std::cout << "--- B+ Tree (Order: " << max_children << ") ---" << std::endl; if (!root) { std::cout << "Tree is empty." << std::endl; return; } std::list<std::pair<Node*, int>> queue; // Node and its level queue.push_back({root, 0}); int current_level = 0; std::cout << "Level 0 (Root): "; while (!queue.empty()) { auto [node, level] = queue.front(); queue.pop_front(); if (level > current_level) { std::cout << std::endl; current_level = level; std::cout << "Level " << level << ": "; } std::cout << "["; if(node->is_leaf) { for(size_t i = 0; i < node->element_count(); ++i) { std::cout << "(" << node->keys[i] << ":" << node->values[i] << ")"; if(i < node->element_count() - 1) std::cout << ", "; } std::cout << "|Next: "; if (node->next_leaf) std::cout << node->next_leaf->keys.empty() ? "?" : std::to_string(node->next_leaf->keys[0]); else std::cout << "null"; } else { for(size_t i = 0; i < node->element_count(); ++i) { std::cout << node->keys[i]; if(i < node->element_count() - 1) std::cout << ", "; } std::cout << "|"; } std::cout << "] "; if (!node->is_leaf) { for (Node* child : node->children) { if(child) queue.push_back({child, level + 1}); } } } std::cout << std::endl; // Print leaf list sequence std::cout << "Leaf Sequence: "; Node* leaf = first_leaf; while(leaf) { std::cout << leaf->keys.empty() ? "?" : std::to_string(leaf->keys[0]); if(leaf->next_leaf) std::cout << " -> "; leaf = leaf->next_leaf; } std::cout << std::endl; std::cout << "--- End Tree ---" << std::endl; } // NOTE: Deletion is significantly more complex due to merging and borrowing. // It's omitted here for brevity but would involve similar locking and node pool usage. // void remove(const K& key) { ... } }; // --- Example Usage --- #include <string> #include <thread> #include <vector> void insert_task(BPlusTree<int, std::string>& tree, int start_key, int count) { for (int i = 0; i < count; ++i) { int key = start_key + i; tree.insert(key, "Value_" + std::to_string(key)); // std::cout << "Thread " << std::this_thread::get_id() << " inserted key " << key << std::endl; // Small sleep to encourage interleaving (optional) // std::this_thread::sleep_for(std::chrono::microseconds(10)); } } int main() { try { BPlusTree<int, std::string> tree(4); // Small order for easier visualization // Single thread insertion std::cout << "--- Single Thread Insertions ---" << std::endl; tree.insert(10, "Apple"); tree.insert(20, "Banana"); tree.insert(5, "Orange"); tree.insert(15, "Grape"); tree.insert(25, "Mango"); tree.insert(30, "Peach"); // Causes split tree.insert(1, "Plum"); tree.insert(12, "Lemon"); tree.insert(18, "Lime"); tree.insert(22, "Cherry"); tree.insert(28, "Berry"); tree.insert(17, "Kiwi"); // Causes more splits tree.insert(3, "Fig"); tree.insert(7, "Date"); tree.print(); std::cout << "\n--- Finding Keys ---" << std::endl; std::cout << "Find 15: " << (tree.find(15) ? *tree.find(15) : "Not Found") << std::endl; std::cout << "Find 7: " << (tree.find(7) ? *tree.find(7) : "Not Found") << std::endl; std::cout << "Find 30: " << (tree.find(30) ? *tree.find(30) : "Not Found") << std::endl; std::cout << "Find 100: " << (tree.find(100) ? *tree.find(100) : "Not Found") << std::endl; // Multi-threaded insertion std::cout << "\n--- Multi-Thread Insertions ---" << std::endl; BPlusTree<int, std::string> threaded_tree(5); // Different order std::vector<std::thread> threads; int num_threads = 4; int items_per_thread = 50; for (int i = 0; i < num_threads; ++i) { threads.emplace_back(insert_task, std::ref(threaded_tree), i * items_per_thread, items_per_thread); } for (auto& t : threads) { t.join(); } std::cout << "Multi-threaded insertion complete. Verifying count..." << std::endl; int expected_count = num_threads * items_per_thread; int actual_count = 0; auto leaf = threaded_tree.get_first_leaf(); while(leaf) { actual_count += leaf->element_count(); leaf = leaf->next_leaf; } std::cout << "Expected items: " << expected_count << ", Actual items: " << actual_count << std::endl; if (actual_count == expected_count) { std::cout << "Count matches!" << std::endl; } else { std::cout << "ERROR: Count mismatch!" << std::endl; } // Optional: Print the large threaded tree (can be very long) // threaded_tree.print(); std::cout << "Finding key 75 in threaded tree: " << (threaded_tree.find(75) ? *threaded_tree.find(75) : "Not Found") << std::endl; std::cout << "Finding key 10 in threaded tree: " << (threaded_tree.find(10) ? *threaded_tree.find(10) : "Not Found") << std::endl; } catch (const std::exception& e) { std::cerr << "Exception caught: " << e.what() << std::endl; return 1; } return 0; }Explanation:
BPlusTreeInternal::Node: Represents a node. It usesstd::vectorinternally for keys, values, and children. This is simpler thanstd::arrayfor dynamic resizing during insertion/splitting but might have slightly more overhead. Thekeysandvaluesvectors grow dynamically up to the node's capacity (max_keys).childrenis sized tomax_children.- Memory Pool (
allocate_node,deallocate_node):node_storage: Astd::vector<std::unique_ptr<Node>>owns all allocatedNodeobjects. When theBPlusTreeis destroyed, this vector ensures all nodes are properly deleted.free_list: Astd::stack<Node*>holds pointers to nodes that are currently not in use but are owned bynode_storage.allocate_node: Tries to pop a node pointer fromfree_list. If the list is empty, it creates anew Nodeusingstd::make_unique, moves ownership intonode_storage, and returns the raw pointer. Crucially, it locks the mutex.deallocate_node: Pushes the raw pointer back onto thefree_list. It does not delete the node; ownership remains withnode_storage. It also locks the mutex.
BPlusTreeClass:- Constructor: Initializes the order, calculates
max_keys,min_keys, and sets up the mutex. - Destructor: Relies on
node_storage'sunique_ptrs to clean up memory. insert(key, value):- Acquires the global
tree_mutexusingstd::lock_guard. - Handles the empty tree case by allocating the first node (root/leaf) from the pool.
- Finds the correct leaf node using
find_leaf(which handles its own internal locking for traversal). - Inserts the key/value into the leaf, potentially causing it to overflow.
- Calls
insert_into_nodewhich handles splitting logic.split_childis used recursively if necessary, allocating new nodes from the pool as needed. - The lock is released automatically when the function exits.
- Acquires the global
find(key):- Acquires the global
tree_mutex. - Traverses from the root down to the appropriate leaf.
- Searches within the leaf.
- Releases the lock.
- Acquires the global
split_child: A private helper that performs the node splitting logic. It callsallocate_nodeto get memory for the new sibling node.find_leaf: Traverses the tree to find the correct leaf for a given key. Note thatfind_leafitself locks the mutex briefly during its traversal.
- Constructor: Initializes the order, calculates
- Atomicity: The
std::lock_guard<std::mutex> lock(tree_mutex);at the beginning of public methods (insert,find, etc.) ensures that only one thread can execute the critical sections of these methods at a time. This guarantees that the tree's state remains consistent during operations. - Limited Public Allocations: The
insertandfindmethods themselves do not containnewordeletecalls for nodes. They rely onallocate_nodeanddeallocate_node, which manage the internal pool. The actual dynamic allocation happens within the pool management methods, minimizing the impact during user-facing operations.
Limitations & Potential Improvements:
- Coarse-Grained Locking: The single mutex provides atomicity but severely limits concurrency. Readers block writers, and writers block readers and other writers.
- Deletion Complexity: Deletion involves node merging and key redistribution from siblings, which is significantly more complex to implement correctly, especially with the memory pool and concurrency. It's omitted here.
- Memory Pool Growth: The current pool implementation implicitly grows via
std::vector. A fixed-size pool or a pool with more sophisticated growth/shrinkage strategies could be implemented. - Node Structure: Using
std::vectorinside nodes might be less performant thanstd::arrayfor fixed maximum sizes, especially regarding cache locality. However,std::arrayrequires more careful manual management of element counts vs. vector size. - Error Handling: Allocation failures are handled via exceptions, but more robust handling might be needed depending on the application.
- Iterator Invalidation: Iterators (if implemented) would be invalidated not only by structural changes but potentially by node reuse from the pool.
- Fine-grained Locking: For higher concurrency, node-level locking (or lock-free techniques) could be explored, but this dramatically increases complexity.
-
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.