void insert(Key k, Data & element)
{
    if (empty tree) {
        create root;
	initialize root;
        normal leaf insert;
    } else {
        Find leaf node r to host the <k, &element>;
        if (r is not full) {
            normal leaf insert;
            split = false;
        } else {      // leaf node full
            newNode = new Node;
            initialize newNode;
            newNode->parent = r->parent;
            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
            split = true;
        }

        // handle the split propagate to parent nodes
        // until no split or reach the root node
        while (split && r->parent != 0) {
            r = r->parent;
            if (r is not full) {
		normal internal insert(k, dataptr, newNode)
                r->size ++;
                split = false; 
            } else {
               // altogether there are 4 keys, 4 data pointers
                // and 5 not-null child pointers
                Node * newNewNode = new Node;
                newNewNode->parent = r->parent;
                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;
                split = true;
            }
        }

        // r is the root node and we just splitted r
        if (split) { 
            Node newRoot = new Node;
            newRoot->child[0] = r; //  or root
            newRoot->child[1] = newNode;
            newRoot->key[0] = k;
            newRoot->dataptr[0] = dataptr;
            newRoot->size = 1;
            r->parent = newRoot;
            newNode->parent = newRoot;
            root = newRoot;
        }
    }
}