A B+ tree implementation for chunk indexing. More...

#include <advanced_structures.hpp>

Collaboration diagram for advanced_structures::ChunkBPlusTree< T >:

Classes
struct	Node

Public Member Functions
	ChunkBPlusTree ()
	Constructs a new ChunkBPlusTree object.

void	insert (const T &key)
	Inserts a key into the B+ tree.

bool	search (const T &key) const
	Searches for a key in the B+ tree.

Private Member Functions
void	insert_non_full (std::shared_ptr< Node > node, const T &key)

bool	search_node (const std::shared_ptr< Node > &node, const T &key) const

void	split_child (std::shared_ptr< Node > parent, int index)

Private Attributes
std::shared_ptr< Node >	root

Static Private Attributes
static constexpr int	ORDER = 4

Detailed Description

template<typename T>
class advanced_structures::ChunkBPlusTree< T >

A B+ tree implementation for chunk indexing.

Template Parameters

T	The type of elements stored in the tree

Definition at line 239 of file advanced_structures.hpp.

Constructor & Destructor Documentation

◆ ChunkBPlusTree()

template<typename T >

advanced_structures::ChunkBPlusTree< T >::ChunkBPlusTree ( )

inline

Constructs a new ChunkBPlusTree object.

Definition at line 257 of file advanced_structures.hpp.

257: root(std::make_shared<Node>()) {}

advanced_structures::ChunkBPlusTree::root

std::shared_ptr< Node > root

Definition advanced_structures.hpp:251

Member Function Documentation

◆ insert()

template<typename T >

void advanced_structures::ChunkBPlusTree< T >::insert ( const T & key )

inline

Inserts a key into the B+ tree.

Parameters

key	The key to insert

Definition at line 263 of file advanced_structures.hpp.

                              {
        if (root->keys.empty()) {
            root->keys.push_back(key);
            return;
        }
 
        if (root->keys.size() == ORDER - 1) {
            auto new_root = std::make_shared<Node>(false);
            new_root->children.push_back(root);
            split_child(new_root, 0);
            root = new_root;
        }
        insert_non_full(root, key);
    }

References advanced_structures::ChunkBPlusTree< T >::insert_non_full(), advanced_structures::ChunkBPlusTree< T >::ORDER, advanced_structures::ChunkBPlusTree< T >::root, and advanced_structures::ChunkBPlusTree< T >::split_child().

Referenced by TEST_F(), and TEST_F().

◆ insert_non_full()

template<typename T >

void advanced_structures::ChunkBPlusTree< T >::insert_non_full	(	std::shared_ptr< Node >	node,
		const T &	key
	)

inlineprivate

Definition at line 309 of file advanced_structures.hpp.

                                                                 {
        int i = node->keys.size() - 1;
 
        if (node->is_leaf) {
            node->keys.push_back(T());
            while (i >= 0 && key < node->keys[i]) {
                node->keys[i + 1] = node->keys[i];
                i--;
            }
            node->keys[i + 1] = key;
        } else {
            while (i >= 0 && key < node->keys[i]) {
                i--;
            }
            i++;
 
            if (node->children[i]->keys.size() == ORDER - 1) {
                split_child(node, i);
                if (key > node->keys[i]) {
                    i++;
                }
            }
            insert_non_full(node->children[i], key);
        }
    }

References advanced_structures::ChunkBPlusTree< T >::insert_non_full(), advanced_structures::ChunkBPlusTree< T >::ORDER, and advanced_structures::ChunkBPlusTree< T >::split_child().

Referenced by advanced_structures::ChunkBPlusTree< T >::insert(), and advanced_structures::ChunkBPlusTree< T >::insert_non_full().

◆ search()

template<typename T >

bool advanced_structures::ChunkBPlusTree< T >::search ( const T & key ) const

inline

Searches for a key in the B+ tree.

Parameters

key	The key to search for

Returns: True if the key is found, false otherwise

Definition at line 283 of file advanced_structures.hpp.

                                    {
        if (root == nullptr)
            return false;
 
        return search_node(root, key);
    }

References advanced_structures::ChunkBPlusTree< T >::root, and advanced_structures::ChunkBPlusTree< T >::search_node().

Referenced by TEST_F(), and TEST_F().

◆ search_node()

template<typename T >

bool advanced_structures::ChunkBPlusTree< T >::search_node	(	const std::shared_ptr< Node > &	node,
		const T &	key
	)		const

inlineprivate

Definition at line 335 of file advanced_structures.hpp.

                                                                          {
        int i = 0;
        while (i < node->keys.size() && key > node->keys[i]) {
            i++;
        }
 
        if (i < node->keys.size() && key == node->keys[i]) {
            return true;
        }
 
        if (node->is_leaf) {
            return false;
        }
 
        return search_node(node->children[i], key);
    }

References advanced_structures::ChunkBPlusTree< T >::search_node().

Referenced by advanced_structures::ChunkBPlusTree< T >::search(), and advanced_structures::ChunkBPlusTree< T >::search_node().

◆ split_child()

template<typename T >

void advanced_structures::ChunkBPlusTree< T >::split_child	(	std::shared_ptr< Node >	parent,
		int	index
	)

inlineprivate

Definition at line 291 of file advanced_structures.hpp.

                                                            {
        auto child = parent->children[index];
        auto new_child = std::make_shared<Node>(child->is_leaf);
 
        parent->keys.insert(parent->keys.begin() + index, child->keys[ORDER / 2 - 1]);
 
        parent->children.insert(parent->children.begin() + index + 1, new_child);
 
        new_child->keys.assign(child->keys.begin() + ORDER / 2, child->keys.end());
 
        child->keys.resize(ORDER / 2 - 1);
 
        if (!child->is_leaf) {
            new_child->children.assign(child->children.begin() + ORDER / 2, child->children.end());
            child->children.resize(ORDER / 2);
        }
    }