static int insertByteArrayKey(StorageImpl db, Page pg, int r, BtreeKey ins, int height)
    {
        int nItems = getnItems(pg);
        int size = getSize(pg);
        int n = (height != 0) ? nItems + 1 : nItems;
        byte[] bval = (byte[])ins.key.oval;
        // insert before e[r]
        int len = bval.length;
        if (size + len + (n+1)*strKeySize <= keySpace) { 
            memcpy(pg, r+1, pg, r, n-r, strKeySize);
            size += len;
            setKeyStrOffs(pg, r, keySpace - size);
            setKeyStrSize(pg, r, len);
            setKeyStrOid(pg, r, ins.oid);
            setKeyBytes(pg, keySpace - size, bval);
            nItems += 1;
        } else { // page is full then divide page
            int  pageId = db.allocatePage();
            Page b = db.putPage(pageId);
            int  moved = 0;
            int  inserted = len + strKeySize;
            int  prevDelta = (1 << 31) + 1;

            for (int bn = 0, i = 0; ; bn += 1) {
                int addSize, subSize;
                int j = nItems - i - 1;
                int keyLen = getKeyStrSize(pg, i);
                if (bn == r) {
                    keyLen = len;
                    inserted = 0;
                    addSize = len;
                    if (height == 0) {
                        subSize = 0;
                        j += 1;
                    } else { 
                        subSize = getKeyStrSize(pg, i);
                    }
                } else { 
                    addSize = subSize = keyLen;
                    if (height != 0) {
                        if (i + 1 != r) { 
                            subSize += getKeyStrSize(pg, i+1);
                            j -= 1;
                        } else { 
                            inserted = 0;
                        }
                    }
                }
                int delta = (moved + addSize + (bn+1)*strKeySize) 
                    - (j*strKeySize + size - subSize + inserted);
                if (delta >= -prevDelta) {
                    if (height == 0) { 
                        ins.getByteArray(b, bn-1);
                    } else {
                        Assert.that("String fits in the B-Tree page", 
                                    moved + (bn+1)*strKeySize <= keySpace);
                        if (bn != r) { 
                            ins.getByteArray(pg, i);
                            setKeyStrOid(b, bn, getKeyStrOid(pg, i));
                            size -= keyLen;
                            i += 1;
                        } else {
                            setKeyStrOid(b, bn, ins.oid);
                        }
                    }
                    nItems = compactifyByteArrays(pg, i);             
                    if (bn < r || (bn == r && height == 0)) { 
                        memcpy(pg, r-i+1, pg, r-i, n - r, strKeySize);
                        size += len;
                        nItems += 1;
                        Assert.that("String fits in the B-Tree page", 
                                    size + (n-i+1)*strKeySize <= keySpace);
                        setKeyStrOffs(pg, r-i, keySpace - size);
                        setKeyStrSize(pg, r-i, len);
                        setKeyStrOid(pg, r-i, ins.oid);
                        setKeyBytes(pg, keySpace - size, bval);
                    }
                    setnItems(b, bn);
                    setSize(b, moved);
                    setSize(pg, size);
                    setnItems(pg, nItems);
                    ins.oid = pageId;
                    db.pool.unfix(b);
                    return Btree.op_overflow;
                }
                moved += keyLen;
                prevDelta = delta;
                Assert.that("String fits in the B-Tree page", 
                            moved + (bn+1)*strKeySize <= keySpace);
                setKeyStrSize(b, bn, keyLen);
                setKeyStrOffs(b, bn, keySpace - moved);
                if (bn == r) { 
                    setKeyStrOid(b, bn, ins.oid);
                    setKeyBytes(b, keySpace - moved, bval);
                } else { 
                    setKeyStrOid(b, bn, getKeyStrOid(pg, i));
                    memcpy(b, keySpace - moved, pg, getKeyStrOffs(pg, i), keyLen, 1);
                    size -= keyLen;
                    i += 1;
                }
            }
        }
        setnItems(pg, nItems);
        setSize(pg, size);
        return size + strKeySize*(nItems+1) < keySpace/3 
            ? Btree.op_underflow : Btree.op_done;
    }