tpl_bplus_tree.H File Reference

B+ Tree implementation with linked leaves and configurable degree. More...

#include <algorithm>
#include <concepts>
#include <initializer_list>
#include <iterator>
#include <memory>
#include <optional>
#include <utility>
#include <ah-concepts.H>
#include <ah-errors.H>
#include <ahFunction.H>
#include <tpl_array.H>
#include <tpl_sort_utils.H>

Include dependency graph for tpl_bplus_tree.H:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
struct	Aleph::detail::BPlusTreeNode< Key >
class	Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >
	Generic B+ Tree with configurable minimum degree. More...
class	Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::Iterator
	Lazy iterator over ordered leaf keys. More...

Namespaces
namespace	Aleph
	Main namespace for Aleph-w library functions.
namespace	Aleph::detail

Typedefs
template<typename Key , class Compare = Aleph::less<Key>, size_t MinDegree = 16>
using	Aleph::BPlus_Tree = Gen_BPlus_Tree< Key, Compare, MinDegree >
	Convenient B+ Tree alias.

Functions
template<typename Compare , typename Key >
bool	Aleph::detail::bplus_equiv (const Compare &cmp, const Key &lhs, const Key &rhs)

Detailed Description

B+ Tree implementation with linked leaves and configurable degree.

This header provides Aleph::BPlus_Tree, a multiway search tree where all user keys live in the leaves and internal nodes only store separators. Leaves are linked left-to-right, which makes ordered scans and range queries efficient and easy to express.

The implementation follows the usual B+ Tree invariants:

• each non-root node stores between t - 1 and 2t - 1 keys
• each internal node with k separator keys owns k + 1 children
• leaves are linked in sorted order through a singly linked list
• all leaves appear at the same depth

Author

Leandro Rabindranath León

Definition in file tpl_bplus_tree.H.