3
\$\begingroup\$

I know B+ trees are not meant to be use in memory, but I just implemented it as an exercise. I'm looking for a general review.

#ifndef B_PLUS_TREE_H
#define B_PLUS_TREE_H

#include <vector>
#include <algorithm>

namespace mds {
    template <typename T, typename D, typename Func = std::less<T>>
    class b_plus_tree {

        struct node {
            unsigned       min_degree;
            std::vector<T> keys;
            node           *bro;
            const Func     &cmp;

            node(unsigned pmin_degree, const Func &pcmp)
                : min_degree(pmin_degree),
                  bro(nullptr), 
                  cmp(pcmp)
            { }

            virtual node* split() {
                auto new_node  = create_node(min_degree);
                auto key_begin = keys.begin() + min_degree;

                new_node->keys.assign(
                    std::make_move_iterator(key_begin),
                    std::make_move_iterator(keys.end()));
                keys.erase(key_begin, keys.end());
                return new_node;
            }

            bool index_contains(unsigned index, const T &key) const {
                return index < keys.size()
                    && !cmp(keys[index], key)
                    && !cmp(key, keys[index]);
            }

            bool full() const {
                return keys.size() == (2 * min_degree - 1);
            }

            unsigned find_bound_index(const T &key) const {
                auto bound = std::lower_bound(keys.begin(), keys.end(), key, cmp);
                return std::distance(keys.begin(), bound);
            }

            void split_child(unsigned i) {
                auto left     = child(i);
                auto new_node = left->split();

                keys.insert(keys.begin() + i, left->keys.back());
                childs().insert(childs().begin() + i + 1, new_node);
                if (!left->leaf()) {
                    left->keys.pop_back();
                }
            }

            unsigned size() {
                return keys.size();
            }

            virtual void take_from_rigth(unsigned index) {
                throw std::runtime_error("take_from_rigth(unsigned) is unsupported");
            }
            virtual void take_from_left(unsigned index) {
                throw std::runtime_error("take_from_left(unsigned) is unsupported");
            }
            virtual void merge(unsigned index) {
                throw std::runtime_error("merge(unsigned) is unsupported");
            }
            virtual unsigned fill(unsigned index) {
                throw std::runtime_error("child(unsigned) is unsupported");
            }
            virtual std::vector<node*>& childs() {
                throw std::runtime_error("childs() is unsupported");
            }
            virtual std::vector<D>& data() {
                throw std::runtime_error("data() is unsupported");
            }
            virtual node* child(unsigned i) const {
                throw std::runtime_error("child(unsigned) is unsupported");
            }
            virtual bool insert_index(const T& key, const D& data) {
                throw std::runtime_error("insert_index(const T&, const D&) is unsupported");
            }


            virtual void merge_template(node *p, unsigned index) = 0;
            virtual void take_from_rigth_template(node* parent, unsigned index) = 0;
            virtual void take_from_left_template(node* parent, unsigned index) = 0;
            virtual node* create_node(unsigned min_degree) const = 0;
            virtual bool leaf() const = 0;
            virtual void remove(const T& key) = 0;
            virtual bool insert(const T& key, const D& data) = 0;
            virtual bool insert(T&& key, const D& data) = 0;
            virtual bool insert(const T& key, D&& data) = 0;
            virtual bool insert(T&& key, D&& data) = 0;
            virtual bool contains(const T& key) const = 0;
            virtual void destroy() = 0;

        };

        struct inode : public node {

            std::vector<node*> children;

            inode(unsigned pmin_degree, const Func &pcmp)
                : node(pmin_degree, pcmp)
            { }

            node* split() override {
                auto new_node    = node::split();
                auto child_begin = children.begin() + min_degree;

                new_node->childs().assign(
                    std::make_move_iterator(child_begin),
                    std::make_move_iterator(childs().end()));
                children.erase(child_begin, children.end());
                return new_node;
            }

            node* create_node(unsigned min_degree) const override {
                return new inode(min_degree, cmp);
            }

            bool leaf() const override {
                return false;
            }

            std::vector<node*>& childs() override {
                return children;
            }

            node* child(unsigned i) const override {
                return children[i];
            }

            bool insert(const T& key, const D& data) override {
                return generic_insert(key, data);
            }

            bool insert(T&& key, const D& data) override {
                return generic_insert(std::move(key), data);
            }

            bool insert(const T& key, D&& data) override {
                return generic_insert(key, std::move(data));
            }

            bool insert(T&& key, D&& data) override {
                return generic_insert(std::move(key), std::move(data));
            }

            template<typename TT, typename DD>
            bool generic_insert(TT&& key, DD&& data) {
                auto index = find_bound_index(key);
                if (children[index]->full()) {
                    split_child(index);
                    index += cmp(keys[index], key);
                }
                return children[index]->insert(
                    std::forward<TT>(key),
                    std::forward<DD>(data));
            }

            bool contains(const T& key) const override {
                auto i = find_bound_index(key);
                return children[i]->contains(key);
            }

            void take_from_rigth_template(node* p, unsigned index) override {
                auto right = p->child(index + 1);

                keys.push_back(std::move(p->keys[index]));
                p->keys[index] = std::move(right->keys[0]);
                right->keys.erase(right->keys.begin());

                children.push_back(right->child(0));
                right->childs().erase(right->childs().begin());
            }

            void take_from_left_template(node* p, unsigned index) override {
                auto left = p->child(index - 1);

                keys.insert(keys.begin(), std::move(p->keys[index - 1]));
                p->keys[index - 1] = std::move(left->keys.back());
                children.insert(children.begin(), left->childs().back());

                left->keys.pop_back();
                left->childs().pop_back();
            }

            void merge_template(node *p, unsigned index) override {
                auto rigth = p->child(index + 1);

                keys.push_back(std::move(p->keys[index]));
                p->keys.erase(p->keys.begin() + index);
                p->childs().erase(p->childs().begin() + index + 1);

                children.insert(children.end(),
                    std::make_move_iterator(rigth->childs().begin()),
                    std::make_move_iterator(rigth->childs().end()));

                keys.insert(keys.end(),
                    std::make_move_iterator(rigth->keys.begin()),
                    std::make_move_iterator(rigth->keys.end()));

                delete rigth;
            }

            unsigned fill(unsigned index) {
                auto deg = child(index)->min_degree;
                if (index != size()
                    && deg <= children[index + 1]->size()) {
                    take_from_rigth(index);
                }
                else if (index != 0
                    && deg <= children[index - 1]->size()) {
                    take_from_left(index);
                }
                else {
                    if (index == size()) {
                        --index;
                    }
                    merge(index);
                }
                return index;
            }
            void take_from_rigth(unsigned index) override {
                children[index]->take_from_rigth_template(this, index);
            }

            void take_from_left(unsigned index) override {
                children[index]->take_from_left_template(this, index);
            }

            void merge(unsigned index) override {
                children[index]->merge_template(this, index);
            }

            void remove(const T& key) override {
                auto i   = find_bound_index(key);
                auto deg = child(i)->min_degree;
                if (child(i)->size() < deg) {
                    i = fill(i);
                }
                child(i)->remove(key);
            }

            void destroy() override {
                for (auto c : children) {
                    c->destroy();
                }
                delete this;
            }

        };

        struct lnode : public node {

            std::vector<D> datas;

            lnode(unsigned pmin_degree, const Func &pcmp)
                : node(pmin_degree, pcmp)
            { }

            node* split() override {
                auto new_node   = node::split();
                auto data_begin = data().begin() + min_degree;
                new_node->data().assign(
                    std::make_move_iterator(data_begin),
                    std::make_move_iterator(data().end()));
                data().erase(data_begin, datas.end());

                new_node->bro = bro;
                bro           = new_node;
                return new_node;
            }

            node* create_node(unsigned min_degree) const override {
                return new lnode(min_degree, cmp);
            }

            bool insert(const T& key, const D& data) override {
                return generic_insert(key, data);
            }

            bool insert(T&& key, const D& data) override {
                return generic_insert(std::move(key), data);
            }

            bool insert(const T& key, D&& data) override {
                return generic_insert(key, std::move(data));
            }

            bool insert(T&& key, D&& data) override {
                return generic_insert(std::move(key), std::move(data));
            }

            template<typename TT, typename DD>
            bool generic_insert(TT&& key, DD&& data) {
                auto bound     = find_bound_index(key);
                bool not_equal = !index_contains(bound, key);

                if (not_equal) {
                    keys.insert(keys.begin() + bound,
                        std::forward<TT>(key));
                    datas.insert(datas.begin() + bound,
                        std::forward<DD>(data));
                }
                return not_equal;
            }

            bool leaf() const override {
                return true;
            }
            std::vector<D>& data() override {
                return datas;
            }

            bool contains(const T& key) const override {
                auto i = find_bound_index(key);
                return index_contains(i, key);
            }

            void take_from_rigth_template(node* p, unsigned index) {
                auto right = p->child(index + 1);

                keys.push_back(std::move(right->keys[0]));
                data().push_back(std::move((right->data())[0]));
                right->keys.erase(right->keys.begin());
                right->data().erase(right->data().begin());

                p->keys[index] = keys.back();
            }

            void take_from_left_template(node* p, unsigned index) override {
                auto left = p->child(index - 1);

                keys.insert(keys.begin(), std::move(left->keys.back()));
                datas.insert(datas.begin(), std::move(left->data().back()));
                left->keys.pop_back();
                left->data().pop_back();

                p->keys[index - 1] = left->keys.back();
            }

            void merge_template(node *p, unsigned index) override {
                auto rigth = p->child(index + 1);
                p->keys.erase(p->keys.begin() + index);
                p->childs().erase(p->childs().begin() + index + 1);

                keys.insert(keys.end(),
                    std::make_move_iterator(rigth->keys.begin()),
                    std::make_move_iterator(rigth->keys.end()));

                datas.insert(datas.end(),
                    std::make_move_iterator(rigth->data().begin()),
                    std::make_move_iterator(rigth->data().end()));

                bro = rigth->bro;
                delete rigth;
            }


            void remove(const T& key) override {
                auto i = find_bound_index(key);
                if (index_contains(i, key)) {
                    datas.erase(datas.begin() + i);
                    keys.erase(keys.begin() + i);
                }
            }

            void destroy() override {
                delete this;
            }
        };

        Func     cmp;
        unsigned leaf_degree;
        unsigned in_degree;
        node     *root;

    public:
        b_plus_tree(unsigned l_degree, unsigned i_degree, Func pcmp,
            std::initializer_list<std::pair<T, D>> list)
            : cmp(pcmp),
            root(new lnode(leaf_degree, cmp)),
            in_degree(i_degree),
            leaf_degree(l_degree)
        {
            for (auto e : list) {
                insert(e.first, e.second);
            }
        }

        b_plus_tree(unsigned l_degree, unsigned i_degree,
            std::initializer_list<std::pair<T, D>> list)
            : b_plus_tree(l_degree, i_degree, Func(), list)
        { }

        b_plus_tree(unsigned l_degree, unsigned i_degree, Func f)
            : b_plus_tree(l_degree, i_degree, f, {})
        { }

        b_plus_tree(unsigned l_degree, unsigned i_degree)
            : b_plus_tree(l_degree, i_degree, Func())
        { }

        b_plus_tree(unsigned degree, std::initializer_list<std::pair<T, D>> list)
            : b_plus_tree(degree, (3 * degree) / 2, list)
        { }

        b_plus_tree(unsigned degree, Func f)
            : b_plus_tree(degree, (3 * degree) / 2, Func())
        { }

        b_plus_tree(unsigned degree)
            : b_plus_tree(degree, Func())
        { }

        ~b_plus_tree() {
            root->destroy();
        }

        void remove(const T& key) {
            root->remove(key);
            if (root->size() == 0
                && !root->leaf()) {
                auto tmp = root;
                root = root->child(0);
                delete tmp;
            }
        }

        template<typename TT, typename DD>
        bool insert(TT&& key, DD&& data) {
            if (root->full()) {
                auto new_root = new inode(in_degree, cmp);
                new_root->childs().push_back(root);
                root = new_root;
                new_root->split_child(0);
            }
            return root->insert(
                std::forward<TT>(key),
                std::forward<DD>(data));
        }

        template<typename F>
        void walk(F func) const {
            auto n = root;
            while (!n->leaf()) {
                n = n->child(0);
            }
            while (n != nullptr) {
                for (auto i = 0u; i < n->size(); ++i) {
                    func(n->keys[i], (n->data())[i]);
                }
                n = n->bro;
            }
        }

        bool contains(const T& key) {
            return root->contains(key);
        }

    };
}

#endif /* B_PLUS_TREE_H */
\$\endgroup\$
  • 1
    \$\begingroup\$ FWIW B-Trees can be used well in memory, as long as each node fits within CPU caches. There's still a significant speed difference between SRAM And DRAM, which can be exploited by cache-friendly data structures. \$\endgroup\$ – Tim McNamara Mar 23 '18 at 2:27
  • \$\begingroup\$ Further to what Tim said, I even made one in C# and was completely blown away by the performance difference with the standard collections. Cache is king, as it turns out. \$\endgroup\$ – Seth Aug 31 '18 at 11:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.