I know B-Trees are meant to be used for external memory, but I implement it to understand the algorithms involved in insertion and deletion. Also, I didn't use a vector because I was asked not to use it (I will probably reimplement this using vectors later).namespace mds {    template<typename T, typename Func = std::less<T>>    class b_tree {        struct BNode {            unsigned size;            bool leaf;            T *keys;            BNode** childs;            BNode(bool is_leaf, unsigned degree)                : size(0),                leaf(is_leaf),                keys(new T[2 * degree - 1]),                childs(leaf ? nullptr : new BNode*[2 * degree]) { }            ~BNode() {                delete[] keys;                delete[] childs;            }        };        unsigned size;        unsigned inner_degree;        unsigned leaf_degree;        BNode    *root;        Func     cmp;        template<typename Func>        void in_order_recursive(const BNode *node, const Func& func) const {            auto size   = node->size;            auto keys   = node->keys;            auto childs = node->childs;            if (node->leaf) {                std::for_each(keys, keys + size, func);            }            else {                for (unsigned i = 0; i < node->size; ++i) {                    in_order_recursive(childs[i], func);                    func(keys[i]);                }                in_order_recursive(childs[node->size], func);            }        }        void remove(BNode* node, const T& key) {            auto n = node;            while (!n->leaf) {                auto i = search_index(n, key);                if (equal(n, i, key)) {                    return delete_internal(n, i);                }                auto child = n->childs[i];                auto deg   = degree(child);                if (child->size < deg) {                    i = fill(n, i, deg);                }                n = n->childs[i];            }            auto i = search_index(n, key);            if (equal(n, i, key)) {                node_remove(n, i);                --n->size;                --size;            }        }        void take_from_rigth(BNode *n, unsigned index) {            auto left  = n->childs[index];            auto rigth = n->childs[index + 1];            left->keys[left->size] = std::move(n->keys[index]);            n->keys[index]         = std::move(node_remove(rigth, 0));            if (!left->leaf) {                left->childs[left->size + 1] = rigth->childs[0];                for (auto i = 0; i < rigth->size; ++i) {                    rigth->childs[i] = rigth->childs[i + 1];                }            }            ++left->size;            --rigth->size;        }        void take_from_left(BNode *n, unsigned index) {            auto left  = n->childs[index - 1];            auto rigth = n->childs[index];            node_insert_index(rigth, 0, std::move(n->keys[index - 1]));            n->keys[index - 1] = std::move(left->keys[left->size - 1]);            if (!rigth->leaf) {                auto childs = rigth->childs;                for (auto i = rigth->size + 1; i --> 0; ) {                    childs[i + 1] = childs[i];                }                childs[0] = left->childs[left->size];            }            --left->size;            ++rigth->size;        }        void split_child(BNode *n, unsigned index) {            auto splited    = n->childs[index];            auto deg        = degree(splited);            auto new_child  = new BNode(splited->leaf, deg);            new_child->size = deg - 1;            splited->size   = deg - 1;            for (unsigned i = 0, to = deg - 1; i < to; ++i) {                new_child->keys[i] = std::move(splited->keys[i + deg]);            }            if (!splited->leaf) {                for (unsigned i = 0; i < deg; ++i) {                    new_child->childs[i] = splited->childs[i + deg];                }            }            for (unsigned i = n->size; i > index; --i) {                n->childs[i + 1] = n->childs[i];            }            n->childs[index + 1] = new_child;            node_insert_index(n, index, std::move(splited->keys[deg - 1]));            ++n->size;        }        template<typename TT>        void node_insert_index(BNode *n, unsigned index, TT&& key) {            auto i    = n->size;            auto keys = n->keys;            while (i --> index) {                keys[i + 1] = std::move(keys[i]);            }            keys[index] = std::forward<TT>(key);        }        std::pair<BNode*, unsigned> search(BNode* n, const T& key) const {            auto i = search_index(n, key);            while (!equal(n, i, key)) {                if (n->leaf) {                    return std::make_pair(nullptr, 0);                }                n = n->childs[i];                i = search_index(n, key);            }            return std::make_pair(n, i);        }        bool equal(const BNode *n, unsigned index, const T& key) const {            return index < n->size                && !cmp(n->keys[index], key)                && !cmp(key, n->keys[index]);        }        unsigned search_index(const BNode* n, const T& key) const {            int begin = 0;            int end   = n->size - 1;            auto keys = n->keys;            while (begin <= end) {                unsigned mid = begin + (end - begin) / 2;                if (cmp(keys[mid], key)) {                    begin = mid + 1;                }                else if (cmp(key, keys[mid])) {                    end = mid - 1;                }                else {                    return mid;                }            }            return begin;        }        bool full(const BNode *n) const {            return n->size == (2 * degree(n) - 1);        }        template<typename TT>        bool node_insert(BNode *n, TT&& key) {            auto bound     = search_index(n, key);            bool not_found = !equal(n, bound, key);            if (not_found) {                node_insert_index(n, bound,                    std::forward<TT>(key));                ++n->size;                ++size;            }            return not_found;        }        unsigned degree(const BNode* n) const {            return n->leaf ? leaf_degree : inner_degree;        }        unsigned fill(BNode *n, unsigned index, unsigned deg) {            auto childs = n->childs;            if (index != n->size                && deg <= childs[index + 1]->size) {                take_from_rigth(n, index);            }            else if (index != 0                && deg <= childs[index - 1]->size) {                take_from_left(n, index);            }            else {                if (index == n->size) {                    --index;                }                merge(n, index);            }            return index;        }        void destroy_tree(BNode *n) {            if (!n->leaf) {                for (auto i = 0u; i <= n->size; ++i) {                    destroy_tree(n->childs[i]);                }            }            delete n;        }        template<typename TT>        bool insert_generic(TT&& key) {            if (full(root)) {                auto child      = root;                root            = new BNode(false, inner_degree);                root->childs[0] = child;                split_child(root, 0);            }            auto n = root;            while (!n->leaf) {                auto index = search_index(n, key);                bool found = equal(n, index, key);                if (full(n->childs[index])) {                    split_child(n, index);                    found  = found || equal(n, index, key);                    index += cmp(n->keys[index], key);                }                if (found) {                    return false;                }                n = n->childs[index];            }            return node_insert(n, std::forward<TT>(key));        }        const T& max(BNode* n) const {            while (!n->leaf) {                n = n->childs[n->size];            }            return n->keys[n->size - 1];        }        const T& min(BNode* n) const {            while (!n->leaf) {                n = n->childs[0];            }            return n->keys[0];        }        void delete_internal(BNode *n, unsigned index) {            auto left  = n->childs[index];            auto rigth = n->childs[index + 1];            auto deg   = degree(left);            if (left->size >= deg) {                n->keys[index] = max(left);                remove(left, n->keys[index]);            }            else if (rigth->size >= deg) {                n->keys[index] = min(rigth);                remove(rigth, n->keys[index]);            }            else {                merge(n, index);                remove(left, left->keys[deg - 1]);            }        }        T node_remove(BNode* n, unsigned i) {            T k = std::move(n->keys[i]);            for (auto to = n->size - 1; i < to; ++i) {                n->keys[i] = std::move(n->keys[i + 1]);            }            return k;        }        void merge(BNode *n, unsigned index) {            auto left  = n->childs[index];            auto rigth = n->childs[index + 1];            auto deg   = degree(left);            left->keys[deg - 1] = std::move(node_remove(n, index));            for (auto i = index + 1; i < n->size; ++i) {                n->childs[i] = n->childs[i + 1];            }            if (!rigth->leaf) {                for (auto i = 0; i <= rigth->size; ++i) {                    left->childs[i + deg] = rigth->childs[i];                }            }            for (auto i = 0; i < rigth->size; ++i) {                left->keys[i + deg] = std::move(rigth->keys[i]);            }            --n->size;            left->size += rigth->size + 1;            delete rigth;        }    public:        b_tree(unsigned pleaf_degree, unsigned pinner_degree, Func pcmp)            : leaf_degree(pleaf_degree),            inner_degree(pinner_degree),            root(new BNode(true, leaf_degree)),            cmp(pcmp),            size(0) { }        b_tree(unsigned pleaf_degree, unsigned pinner_degree)            : b_tree(pleaf_degree, pinner_degree, Func()) { }        b_tree(unsigned min_degree)            : b_tree((3 * min_degree) / 2, min_degree) { }        ~b_tree() {            destroy_tree(root);        }        void remove(const T& key) {            remove(root, key);            if (root->size == 0 && !root->leaf) {                auto tmp = root;                root     = root->childs[0];                delete tmp;            }        }        unsigned len() const {            return size;        }        bool insert(T&& key) {            return insert_generic(std::move(key));        }        bool contains(const T& key) {            return search(root, key).first != nullptr;        }        bool insert(const T& key) {            return insert_generic(key);        }        template<typename Func>        void in_order_walk(const Func& func) const {            in_order_recursive(root, func);        }        bool empty() {            return size == 0;        }    };}
In-memory B-Tree
c++;performance;c++11;tree;c++14