The first half of the algorithm is pretty easy. Since all the data is stored at the leaves, we just do the "interior node" part of the find, to locate the leaf in which this data should be stored. In the leaf we just do a linear search until we find the right spot to put the new data.
Note, this might mean having to moved some/most/all of the rest of the data in this leaf, to keep the items in order. But, we're happy to do almost any kind of O(n) processing if we can avoid disk hits.
The only trick is what if there is already m things in this leaf. Well, then only m things are allowed in the leaf, and this would be the m+1th. No good.