void insert(Key k, Data & element)
{
    if (root == 0) { // empty tree
        root = new Node;
        initialize node;
        normal leaf node insert (k, &element);
    } else { // not empty
        Node *newNode = 0;
        Data * dataptr = & element;
        bool split = insert(root, k, dataptr, newNode);
        if (split) { // root got splitted
            Node *newRoot = new Node;
            newRoot->size = 1;
            newRoot->child[0] = root;
            newRoot->key[0] = k;
            newRoot->data[0] = dataptr;
            newRoot->child[1] = newNode;
            root = newRoot;
        }
    }
}

bool insert(Node *r, int & k, Data * & dataptr, Node * & newNode)
{
    if (r->child[0] == 0) { // leaf node
        if (r->size < capacity) { // leaf node not full
            normal leaf insert (k, dataptr);
            r->size ++;
            return false;
        } else { // leaf node full
            // altogether there are 4 keys, 4 data pointers
            newNode = new Node;
            initialize newNode;
            distribute <key, dp> pairs and <k, dataptr> into node r and newNode;
            r->size = 2;
            newNode->size = 1;
            k = third key
            dataptr = third data pointer
            return true;
        }
    } else { // internal node
        find the subtree p to insert the <k, dataptr> pair
        bool split = insert(r->child[p], k, dataptr, newNode);
        if (split) { // child wants to put a new combo to this node
            if (r->size < capacity) { // internal node not full
                normal internal insert(k, dataptr, newNode, p);
                r->size ++;
                return false;
            } else { // internal node full
                // altogether there are 4 keys, 4 data pointers
                // and 5 not-null child pointers
                Node * newNewNode = new Node;
                in node r, keep 2 keys, 2 data pointers and 3 child pointers
                in newNewNode, keep 1 key, 1 data pointer and 2 child pointers
                // the last 2 child node's parent pointer pointing to newNewNode
                r->size = 2;
                newNewNode->size = 1;
                k = third key
                dataptr = third data pointer
                newNode = newNewNode;
                return true;
            }
        }
    }
    return false;
}