static int insert(StorageImpl db, int pageId, Btree tree, BtreeKey ins, int height, 
                      boolean unique, boolean overwrite)
    {
        Page pg = db.getPage(pageId);
        int result;
        int l = 0, n = getnItems(pg), r = n;
        int ahead = unique ? 1 : 0;
        try { 
            if (tree.type == ClassDescriptor.tpString) {         
                while (l < r)  {
                    int i = (l+r) >> 1;
                    if (compareStr(ins.key, pg, i) >= ahead) { 
                        l = i+1; 
                    } else { 
                        r = i;
                    }
                }
                Assert.that(l == r);
                if (--height != 0) { 
                    result = insert(db, getKeyStrOid(pg, r), tree, ins, height, unique, overwrite);
                    Assert.that(result != Btree.op_not_found);
                    if (result != Btree.op_overflow) {
                        return result;                              
                    }                                             
                } else if (r < n && compareStr(ins.key, pg, r) == 0) {
                    if (overwrite) { 
                        db.pool.unfix(pg);
                        pg = null;
                        pg = db.putPage(pageId);
                        ins.oldOid = getKeyStrOid(pg, r);
                        setKeyStrOid(pg, r, ins.oid);
                        return Btree.op_overwrite;
                    } else if (unique) { 
                        return Btree.op_duplicate;
                    }
                }
                db.pool.unfix(pg);
                pg = null;
                pg = db.putPage(pageId);
                return insertStrKey(db, pg, r, ins, height);
            } else if (tree.type == ClassDescriptor.tpArrayOfByte) {         
                while (l < r)  {
                    int i = (l+r) >> 1;
                    if (tree.compareByteArrays(ins.key, pg, i) >= ahead) { 
                        l = i+1; 
                    } else { 
                        r = i;
                    }
                }
                Assert.that(l == r);
                if (--height != 0) { 
                    result = insert(db, getKeyStrOid(pg, r), tree, ins, height, unique, overwrite);
                    Assert.that(result != Btree.op_not_found);
                    if (result != Btree.op_overflow) {
                        return result;                              
                    }                                             
                } else if (r < n && tree.compareByteArrays(ins.key, pg, r) == 0) {
                    if (overwrite) { 
                        db.pool.unfix(pg);
                        pg = null;
                        pg = db.putPage(pageId);
                        ins.oldOid = getKeyStrOid(pg, r);
                        setKeyStrOid(pg, r, ins.oid);
                        return Btree.op_overwrite;
                    } else if (unique) { 
                        return Btree.op_duplicate;
                    }
                }
                db.pool.unfix(pg);
                pg = null;
                pg = db.putPage(pageId);
                return insertByteArrayKey(db, pg, r, ins, height);
            } else { 
                while (l < r)  {
                    int i = (l+r) >> 1;
                    if (compare(ins.key, pg, i) >= ahead) l = i+1; else r = i;
                }
                Assert.that(l == r);
                /* insert before e[r] */
                if (--height != 0) {
                    result = insert(db, getReference(pg, maxItems-r-1), tree, ins, height, unique, overwrite);
                    Assert.that(result != Btree.op_not_found);
                    if (result != Btree.op_overflow) {
                        return result;
                    }
                    n += 1;
                } else if (r < n && compare(ins.key, pg, r) == 0) { 
                    if (overwrite) { 
                        db.pool.unfix(pg);
                        pg = null;
                        pg = db.putPage(pageId);
                        ins.oldOid = getReference(pg, maxItems-r-1);
                        setReference(pg, maxItems-r-1, ins.oid);
                        return Btree.op_overwrite;
                    } else if (unique) { 
                        return Btree.op_duplicate;
                    }
                }
                db.pool.unfix(pg);
                pg = null;
                pg = db.putPage(pageId);
                int itemSize = ClassDescriptor.sizeof[tree.type];
                int max = keySpace / (4 + itemSize);
                if (n < max) {
                    memcpy(pg, r+1, pg, r, n - r, itemSize);
                    memcpy(pg, maxItems-n-1, pg, maxItems-n, n-r, 4);
                    ins.pack(pg, r);
                    setnItems(pg, getnItems(pg)+1);
                    return Btree.op_done;
                } else { /* page is full then divide page */
                    pageId = db.allocatePage();
                    Page b = db.putPage(pageId);
                    Assert.that(n == max);
                    int m = (max+1)/2;
                    if (r < m) {
                        memcpy(b, 0, pg, 0, r, itemSize);
                        memcpy(b, r+1, pg, r, m-r-1, itemSize);
                        memcpy(pg, 0, pg, m-1, max-m+1, itemSize);
                        memcpy(b, maxItems-r, pg, maxItems-r, r, 4);
                        ins.pack(b, r);
                        memcpy(b, maxItems-m, pg, maxItems-m+1, m-r-1, 4);
                        memcpy(pg, maxItems-max+m-1, pg, maxItems-max, max-m+1, 4);
                    } else {
                        memcpy(b, 0, pg, 0, m, itemSize);
                        memcpy(pg, 0, pg, m, r-m, itemSize);
                        memcpy(pg, r-m+1, pg, r, max-r, itemSize);
                        memcpy(b, maxItems-m, pg, maxItems-m, m, 4);
                        memcpy(pg, maxItems-r+m, pg, maxItems-r, r-m, 4);
                        ins.pack(pg, r-m);
                        memcpy(pg, maxItems-max+m-1, pg, maxItems-max, max-r, 4);
                    }
                    ins.oid = pageId;
                    ins.extract(b, firstKeyOffs + (m-1)*itemSize, tree.type);
                    if (height == 0) {
                        setnItems(pg, max - m + 1);
                        setnItems(b, m);
                    } else {
                        setnItems(pg, max - m);
                        setnItems(b, m - 1);
                    }                            
                    db.pool.unfix(b);
                    return Btree.op_overflow;
                }
            }
        } finally { 
            if (pg != null) { 
                db.pool.unfix(pg);
            }
        }
    }