dead simple b plus tree insertion

bplus.cpp

const int M = 4;

template <class K, class V>
struct node;

template <class K, class V>
struct entry {
    K key;
    V value;
    node<K,V>* next;
    entry(K k = K(), V v = V(), node<K,V>* n = nullptr) : key(k), value(v), next(n) { }
};


template <class K, class V>
struct node {
    entry<K,V> b[M];
    int n;
    node* next;
    node(int k = 0) {
        n = k;
    }
};


template <class K, class V>
class btree {
    private:
        using bpentry = entry<K,V>;
        using bpnode = node<K,V>;
        bpnode* root;
        int height;
        int count;
        V nullItem;
        void inorder(bpnode* node, int ht) {
            if (ht == 0) {
                for (bpnode* it = node; it != nullptr; it = it->next) {
                    cout<<"(";
                    for (int i = 0; i < it->n; i++) {
                        cout<<it->b[i].key<<" ";
                    }
                    if (it->next)
                    cout<<") -> ";
                    else cout<<")";
                }
                cout<<endl;
            } else {
                inorder(node->b[0].next, ht-1);
            }
        }
        bpnode* split(bpnode* node) {
            bpnode* nn = new bpnode(M/2);
            for (int j = 0; j < M/2; j++) {
                nn->b[j] = node->b[M/2+j];
            }
            node->n = M/2;
            nn->next = node->next;
            node->next = nn;
            return nn;
        }
        bpnode* insert(bpnode* node, K key, V value, int ht) {
            int i, j; bpentry nent(key, value, nullptr);
            if (ht == 0) {
                for (j = 0; j < node->n; j++)
                   if (key < node->b[j].key)
                        break;
            } else {
                for (j = 0; j < node->n; j++)
                    if (j+1 == node->n || key < node->b[j+1].key) {
                        cout<<key<<"<"<<node->b[j+1].key<<"?"<<endl;
                        bpnode* u = insert(node->b[j++].next, key, value, ht-1);
                        if (u == nullptr) return nullptr;
                        nent = bpentry(u->b[0].key, nullItem, u);
                        break;
                    }
            }
            for (i = node->n; i > j; i--)
                node->b[i] = node->b[i-1];
            node->b[i] = nent;
            node->n++;
            if (node->n < M) return nullptr;
            else return split(node);
        }
    public:
        btree() {
            root = new bpnode(0);
            height = 0;
        }
        void insert(K key, V value) {
            bpnode* tmp = insert(root, key, value, height);
            count++;
            if (tmp == nullptr) return;
            bpnode* oldroot = root;
            root = new bpnode(2);
            root->b[0].key = oldroot->b[0].key;
            root->b[0].next = oldroot;
            root->b[1].key = tmp->b[0].key;
            root->b[1].next = tmp;
            height++;
        }
        void show() {
            inorder(root, height);
        }
};