static int handlePageUnderflow(StorageImpl db, Page pg, int r, int type, BtreeKey rem, int height)
    {
        int nItems = getnItems(pg);
        if (type == ClassDescriptor.tpString) { 
            Page a = db.putPage(getKeyStrOid(pg, r));
            int an = getnItems(a);
            if (r < nItems) { // exists greater page
                Page b = db.getPage(getKeyStrOid(pg, r+1));
                int bn = getnItems(b); 
                int merged_size = (an+bn)*strKeySize + getSize(a) + getSize(b);
                if (height != 1) { 
                    merged_size += getKeyStrSize(pg, r)*2 + strKeySize*2;
                }
                if (merged_size > keySpace) {
                    // reallocation of nodes between pages a and b
                    int i, j, k;
                    db.pool.unfix(b);
                    b = db.putPage(getKeyStrOid(pg, r+1));
                    int size_a = getSize(a);
                    int size_b = getSize(b);
                    int addSize, subSize;
                    if (height != 1) {
                        addSize = getKeyStrSize(pg, r);
                        subSize = getKeyStrSize(b, 0);
                    } else { 
                        addSize = subSize = getKeyStrSize(b, 0);
                    }
                    i = 0;
                    int prevDelta = (an*strKeySize + size_a) - (bn*strKeySize + size_b);
                    while (true) { 
                        i += 1;
                        int delta = ((an+i)*strKeySize + size_a + addSize*2)
                            - ((bn-i)*strKeySize + size_b - subSize*2);
                        if (delta >= 0) {
                            if (delta >= -prevDelta) { 
                                i -= 1;
                            }
                            break;
                        }
                        size_a += addSize*2;
                        size_b -= subSize*2;
                        prevDelta = delta;
                        if (height != 1) { 
                            addSize = subSize;  
                            subSize = getKeyStrSize(b, i);
                        } else { 
                            addSize = subSize = getKeyStrSize(b, i);
                        }
                    }
                    int result = Btree.op_done;
                    if (i > 0) { 
                        k = i;
                        if (height != 1) { 
                            int len = getKeyStrSize(pg, r);
                            setSize(a, getSize(a) + len*2);
                            setKeyStrOffs(a, an, keySpace - getSize(a));
                            setKeyStrSize(a, an, len);
                            memcpy(a, getKeyStrOffs(a, an),
                                   pg, getKeyStrOffs(pg, r), len*2, 1);
                            k -= 1;
                            an += 1;
                            setKeyStrOid(a, an+k, getKeyStrOid(b, k));
                            setSize(b, getSize(b) - getKeyStrSize(b, k)*2);
                        }
                        for (j = 0; j < k; j++) { 
                            int len = getKeyStrSize(b, j);
                            setSize(a, getSize(a) + len*2);
                            setSize(b, getSize(b) - len*2);
                            setKeyStrOffs(a, an, keySpace - getSize(a));
                            setKeyStrSize(a, an, len);
                            setKeyStrOid(a, an, getKeyStrOid(b, j));
                            memcpy(a, getKeyStrOffs(a, an),
                                   b, getKeyStrOffs(b, j), len*2, 1);
                            an += 1;
                        }
                        rem.getStr(b, i-1);
                        result = replaceStrKey(db, pg, r, rem, height);
                        setnItems(a, an);
                        setnItems(b, compactifyStrings(b, i));
                    }
                    db.pool.unfix(a);
                    db.pool.unfix(b);
                    return result;
                } else { // merge page b to a
                    if (height != 1) { 
                        int r_len = getKeyStrSize(pg, r);
                        setKeyStrSize(a, an, r_len);
                        setSize(a, getSize(a) + r_len*2);
                        setKeyStrOffs(a, an, keySpace - getSize(a));
                        memcpy(a, getKeyStrOffs(a, an), 
                               pg, getKeyStrOffs(pg, r), r_len*2, 1);
                        an += 1;
                        setKeyStrOid(a, an+bn, getKeyStrOid(b, bn));
                    }
                    for (int i = 0; i < bn; i++, an++) { 
                        setKeyStrSize(a, an, getKeyStrSize(b, i));
                        setKeyStrOffs(a, an, getKeyStrOffs(b, i) - getSize(a));
                        setKeyStrOid(a, an, getKeyStrOid(b, i));
                    }
                    setSize(a, getSize(a) + getSize(b));
                    setnItems(a, an);
                    memcpy(a, keySpace - getSize(a), b, keySpace - getSize(b), getSize(b), 1);
                    db.pool.unfix(a);
                    db.pool.unfix(b);
                    db.freePage(getKeyStrOid(pg, r+1));
                    setKeyStrOid(pg, r+1, getKeyStrOid(pg, r));
                    return removeStrKey(pg, r);
                }
            } else { // page b is before a
                Page b = db.getPage(getKeyStrOid(pg, r-1));
                int bn = getnItems(b); 
                int merged_size = (an+bn)*strKeySize + getSize(a) + getSize(b);
                if (height != 1) { 
                    merged_size += getKeyStrSize(pg, r-1)*2 + strKeySize*2;
                }
                if (merged_size > keySpace) {
                    // reallocation of nodes between pages a and b
                    int i, j, k, len;
                    db.pool.unfix(b);
                    b = db.putPage(getKeyStrOid(pg, r-1));
                    int size_a = getSize(a);
                    int size_b = getSize(b);
                    int addSize, subSize;
                    if (height != 1) {
                        addSize = getKeyStrSize(pg, r-1);
                        subSize = getKeyStrSize(b, bn-1);
                    } else { 
                        addSize = subSize = getKeyStrSize(b, bn-1);
                    }
                    i = 0;
                    int prevDelta = (an*strKeySize + size_a) - (bn*strKeySize + size_b);
                    while (true) { 
                        i += 1;
                        int delta = ((an+i)*strKeySize + size_a + addSize*2)
                            - ((bn-i)*strKeySize + size_b - subSize*2);
                        if (delta >= 0) {
                            if (delta >= -prevDelta) { 
                                i -= 1;
                            }
                            break;
                        }
                        prevDelta = delta;
                        size_a += addSize*2;
                        size_b -= subSize*2;
                        if (height != 1) { 
                            addSize = subSize;  
                            subSize = getKeyStrSize(b, bn-i-1);
                        } else { 
                            addSize = subSize = getKeyStrSize(b, bn-i-1);
                        }
                    }
                    int result = Btree.op_done;
                    if (i > 0) { 
                        k = i;
                        Assert.that(i < bn);
                        if (height != 1) { 
                            setSize(b, getSize(b) - getKeyStrSize(b, bn-k)*2);
                            memcpy(a, i, a, 0, an+1, strKeySize);
                            k -= 1;
                            setKeyStrOid(a, k, getKeyStrOid(b, bn));
                            len = getKeyStrSize(pg, r-1);
                            setKeyStrSize(a, k, len);
                            setSize(a, getSize(a) + len*2);
                            setKeyStrOffs(a, k, keySpace - getSize(a));
                            memcpy(a, getKeyStrOffs(a, k), 
                                   pg, getKeyStrOffs(pg, r-1), len*2, 1);
                        } else { 
                            memcpy(a, i, a, 0, an, strKeySize);
                        }
                        for (j = 0; j < k; j++) { 
                            len = getKeyStrSize(b, bn-k+j);
                            setSize(a, getSize(a) + len*2);
                            setSize(b, getSize(b) - len*2);
                            setKeyStrOffs(a, j, keySpace - getSize(a));
                            setKeyStrSize(a, j, len);
                            setKeyStrOid(a, j, getKeyStrOid(b, bn-k+j));
                            memcpy(a, getKeyStrOffs(a, j),
                                   b, getKeyStrOffs(b, bn-k+j), len*2, 1);
                        }
                        an += i;
                        setnItems(a, an);
                        rem.getStr(b, bn-k-1);
                        result = replaceStrKey(db, pg, r-1, rem, height);
                        setnItems(b, compactifyStrings(b, -i));
                    }
                    db.pool.unfix(a);
                    db.pool.unfix(b);               
                    return result;
                } else { // merge page b to a
                    if (height != 1) { 
                        memcpy(a, bn + 1, a, 0, an+1, strKeySize);
                        int len = getKeyStrSize(pg, r-1);
                        setKeyStrSize(a, bn, len);
                        setSize(a, getSize(a) + len*2);
                        setKeyStrOffs(a, bn, keySpace - getSize(a));
                        setKeyStrOid(a, bn, getKeyStrOid(b, bn));
                        memcpy(a, getKeyStrOffs(a, bn), 
                               pg, getKeyStrOffs(pg, r-1), len*2, 1);
                        an += 1;
                    } else { 
                        memcpy(a, bn, a, 0, an, strKeySize);
                    }
                    for (int i = 0; i < bn; i++) { 
                        setKeyStrOid(a, i, getKeyStrOid(b, i));
                        setKeyStrSize(a, i, getKeyStrSize(b, i));
                        setKeyStrOffs(a, i, getKeyStrOffs(b, i) - getSize(a));
                    }
                    an += bn;
                    setnItems(a, an);
                    setSize(a, getSize(a) + getSize(b));
                    memcpy(a, keySpace - getSize(a), b, keySpace - getSize(b), getSize(b), 1);
                    db.pool.unfix(a);
                    db.pool.unfix(b);
                    db.freePage(getKeyStrOid(pg, r-1));
                    return removeStrKey(pg, r-1);
                }
            }
        } else if (type == ClassDescriptor.tpArrayOfByte) { 
            Page a = db.putPage(getKeyStrOid(pg, r));
            int an = getnItems(a);
            if (r < nItems) { // exists greater page
                Page b = db.getPage(getKeyStrOid(pg, r+1));
                int bn = getnItems(b); 
                int merged_size = (an+bn)*strKeySize + getSize(a) + getSize(b);
                if (height != 1) { 
                    merged_size += getKeyStrSize(pg, r) + strKeySize*2;
                }
                if (merged_size > keySpace) {
                    // reallocation of nodes between pages a and b
                    int i, j, k;
                    db.pool.unfix(b);
                    b = db.putPage(getKeyStrOid(pg, r+1));
                    int size_a = getSize(a);
                    int size_b = getSize(b);
                    int addSize, subSize;
                    if (height != 1) {
                        addSize = getKeyStrSize(pg, r);
                        subSize = getKeyStrSize(b, 0);
                    } else { 
                        addSize = subSize = getKeyStrSize(b, 0);
                    }
                    i = 0;
                    int prevDelta = (an*strKeySize + size_a) - (bn*strKeySize + size_b);
                    while (true) { 
                        i += 1;
                        int delta = ((an+i)*strKeySize + size_a + addSize)
                            - ((bn-i)*strKeySize + size_b - subSize);
                        if (delta >= 0) {
                            if (delta >= -prevDelta) { 
                                i -= 1;
                            }
                            break;
                        }
                        size_a += addSize;
                        size_b -= subSize;
                        prevDelta = delta;
                        if (height != 1) { 
                            addSize = subSize;  
                            subSize = getKeyStrSize(b, i);
                        } else { 
                            addSize = subSize = getKeyStrSize(b, i);
                        }
                    }
                    int result = Btree.op_done;
                    if (i > 0) { 
                        k = i;
                        if (height != 1) { 
                            int len = getKeyStrSize(pg, r);
                            setSize(a, getSize(a) + len);
                            setKeyStrOffs(a, an, keySpace - getSize(a));
                            setKeyStrSize(a, an, len);
                            memcpy(a, getKeyStrOffs(a, an),
                                   pg, getKeyStrOffs(pg, r), len, 1);
                            k -= 1;
                            an += 1;
                            setKeyStrOid(a, an+k, getKeyStrOid(b, k));
                            setSize(b, getSize(b) - getKeyStrSize(b, k));
                        }
                        for (j = 0; j < k; j++) { 
                            int len = getKeyStrSize(b, j);
                            setSize(a, getSize(a) + len);
                            setSize(b, getSize(b) - len);
                            setKeyStrOffs(a, an, keySpace - getSize(a));
                            setKeyStrSize(a, an, len);
                            setKeyStrOid(a, an, getKeyStrOid(b, j));
                            memcpy(a, getKeyStrOffs(a, an),
                                   b, getKeyStrOffs(b, j), len, 1);
                            an += 1;
                        }
                        rem.getByteArray(b, i-1);
                        result = replaceByteArrayKey(db, pg, r, rem, height);
                        setnItems(a, an);
                        setnItems(b, compactifyByteArrays(b, i));
                    }
                    db.pool.unfix(a);
                    db.pool.unfix(b);
                    return result;
                } else { // merge page b to a
                    if (height != 1) { 
                        int r_len = getKeyStrSize(pg, r);
                        setKeyStrSize(a, an, r_len);
                        setSize(a, getSize(a) + r_len);
                        setKeyStrOffs(a, an, keySpace - getSize(a));
                        memcpy(a, getKeyStrOffs(a, an), 
                               pg, getKeyStrOffs(pg, r), r_len, 1);
                        an += 1;
                        setKeyStrOid(a, an+bn, getKeyStrOid(b, bn));
                    }
                    for (int i = 0; i < bn; i++, an++) { 
                        setKeyStrSize(a, an, getKeyStrSize(b, i));
                        setKeyStrOffs(a, an, getKeyStrOffs(b, i) - getSize(a));
                        setKeyStrOid(a, an, getKeyStrOid(b, i));
                    }
                    setSize(a, getSize(a) + getSize(b));
                    setnItems(a, an);
                    memcpy(a, keySpace - getSize(a), b, keySpace - getSize(b), getSize(b), 1);
                    db.pool.unfix(a);
                    db.pool.unfix(b);
                    db.freePage(getKeyStrOid(pg, r+1));
                    setKeyStrOid(pg, r+1, getKeyStrOid(pg, r));
                    return removeByteArrayKey(pg, r);
                }
            } else { // page b is before a
                Page b = db.getPage(getKeyStrOid(pg, r-1));
                int bn = getnItems(b); 
                int merged_size = (an+bn)*strKeySize + getSize(a) + getSize(b);
                if (height != 1) { 
                    merged_size += getKeyStrSize(pg, r-1) + strKeySize*2;
                }
                if (merged_size > keySpace) {
                    // reallocation of nodes between pages a and b
                    int i, j, k, len;
                    db.pool.unfix(b);
                    b = db.putPage(getKeyStrOid(pg, r-1));
                    int size_a = getSize(a);
                    int size_b = getSize(b);
                    int addSize, subSize;
                    if (height != 1) {
                        addSize = getKeyStrSize(pg, r-1);
                        subSize = getKeyStrSize(b, bn-1);
                    } else { 
                        addSize = subSize = getKeyStrSize(b, bn-1);
                    }
                    i = 0;
                    int prevDelta = (an*strKeySize + size_a) - (bn*strKeySize + size_b);
                    while (true) { 
                        i += 1;
                        int delta = ((an+i)*strKeySize + size_a + addSize)
                            - ((bn-i)*strKeySize + size_b - subSize);
                        if (delta >= 0) {
                            if (delta >= -prevDelta) { 
                                i -= 1;
                            }
                            break;
                        }
                        prevDelta = delta;
                        size_a += addSize;
                        size_b -= subSize;
                        if (height != 1) { 
                            addSize = subSize;  
                            subSize = getKeyStrSize(b, bn-i-1);
                        } else { 
                            addSize = subSize = getKeyStrSize(b, bn-i-1);
                        }
                    }
                    int result = Btree.op_done;
                    if (i > 0) { 
                        k = i;
                        Assert.that(i < bn);
                        if (height != 1) { 
                            setSize(b, getSize(b) - getKeyStrSize(b, bn-k));
                            memcpy(a, i, a, 0, an+1, strKeySize);
                            k -= 1;
                            setKeyStrOid(a, k, getKeyStrOid(b, bn));
                            len = getKeyStrSize(pg, r-1);
                            setKeyStrSize(a, k, len);
                            setSize(a, getSize(a) + len);
                            setKeyStrOffs(a, k, keySpace - getSize(a));
                            memcpy(a, getKeyStrOffs(a, k), 
                                   pg, getKeyStrOffs(pg, r-1), len, 1);
                        } else { 
                            memcpy(a, i, a, 0, an, strKeySize);
                        }
                        for (j = 0; j < k; j++) { 
                            len = getKeyStrSize(b, bn-k+j);
                            setSize(a, getSize(a) + len);
                            setSize(b, getSize(b) - len);
                            setKeyStrOffs(a, j, keySpace - getSize(a));
                            setKeyStrSize(a, j, len);
                            setKeyStrOid(a, j, getKeyStrOid(b, bn-k+j));
                            memcpy(a, getKeyStrOffs(a, j),
                                   b, getKeyStrOffs(b, bn-k+j), len, 1);
                        }
                        an += i;
                        setnItems(a, an);
                        rem.getByteArray(b, bn-k-1);
                        result = replaceByteArrayKey(db, pg, r-1, rem, height);
                        setnItems(b, compactifyByteArrays(b, -i));
                    }
                    db.pool.unfix(a);
                    db.pool.unfix(b);               
                    return result;
                } else { // merge page b to a
                    if (height != 1) { 
                        memcpy(a, bn + 1, a, 0, an+1, strKeySize);
                        int len = getKeyStrSize(pg, r-1);
                        setKeyStrSize(a, bn, len);
                        setSize(a, getSize(a) + len);
                        setKeyStrOffs(a, bn, keySpace - getSize(a));
                        setKeyStrOid(a, bn, getKeyStrOid(b, bn));
                        memcpy(a, getKeyStrOffs(a, bn), 
                               pg, getKeyStrOffs(pg, r-1), len, 1);
                        an += 1;
                    } else { 
                        memcpy(a, bn, a, 0, an, strKeySize);
                    }
                    for (int i = 0; i < bn; i++) { 
                        setKeyStrOid(a, i, getKeyStrOid(b, i));
                        setKeyStrSize(a, i, getKeyStrSize(b, i));
                        setKeyStrOffs(a, i, getKeyStrOffs(b, i) - getSize(a));
                    }
                    an += bn;
                    setnItems(a, an);
                    setSize(a, getSize(a) + getSize(b));
                    memcpy(a, keySpace - getSize(a), b, keySpace - getSize(b), getSize(b), 1);
                    db.pool.unfix(a);
                    db.pool.unfix(b);
                    db.freePage(getKeyStrOid(pg, r-1));
                    return removeByteArrayKey(pg, r-1);
                }
            }
        } else { // scalar types
            Page a = db.putPage(getReference(pg, maxItems-r-1));
            int an = getnItems(a);
            int itemSize = ClassDescriptor.sizeof[type];
            if (r < nItems) { // exists greater page
                Page b = db.getPage(getReference(pg, maxItems-r-2));
                int bn = getnItems(b); 
                Assert.that(bn >= an);
                if (height != 1) { 
                    memcpy(a, an, pg, r, 1, itemSize);
                    an += 1;
                    bn += 1;
                }
                int merged_size = (an+bn)*(4 + itemSize);
                if (merged_size > keySpace) { 
                    // reallocation of nodes between pages a and b
                    int i = bn - ((an + bn) >> 1);
                    db.pool.unfix(b);
                    b = db.putPage(getReference(pg, maxItems-r-2));
                    memcpy(a, an, b, 0, i, itemSize);
                    memcpy(b, 0, b, i, bn-i, itemSize);
                    memcpy(a, maxItems-an-i, b, maxItems-i, i, 4);
                    memcpy(b, maxItems-bn+i, b, maxItems-bn, bn-i, 4);
                    memcpy(pg, r, a, an+i-1, 1, itemSize);
                    setnItems(b, getnItems(b) - i);
                    setnItems(a, getnItems(a) + i);
                    db.pool.unfix(a);
                    db.pool.unfix(b);
                    return Btree.op_done;
                } else { // merge page b to a  
                    memcpy(a, an, b, 0, bn, itemSize);
                    memcpy(a, maxItems-an-bn, b, maxItems-bn, bn, 4);
                    db.freePage(getReference(pg, maxItems-r-2));
                    memcpy(pg, maxItems-nItems, pg, maxItems-nItems-1, 
                           nItems - r - 1, 4);
                    memcpy(pg, r, pg, r+1, nItems - r - 1, itemSize);
                    setnItems(a, getnItems(a) + bn);
                    setnItems(pg, nItems - 1);
                    db.pool.unfix(a);
                    db.pool.unfix(b);
                    return nItems*(itemSize + 4) < keySpace/3
                        ? Btree.op_underflow : Btree.op_done;
                }
            } else { // page b is before a
                Page b = db.getPage(getReference(pg, maxItems-r));
                int bn = getnItems(b); 
                Assert.that(bn >= an);
                if (height != 1) { 
                    an += 1;
                    bn += 1;
                }
                int merged_size = (an+bn)*(4 + itemSize);
                if (merged_size > keySpace) { 
                    // reallocation of nodes between pages a and b
                    int i = bn - ((an + bn) >> 1);
                    db.pool.unfix(b);
                    b = db.putPage(getReference(pg, maxItems-r));
                    memcpy(a, i, a, 0, an, itemSize);
                    memcpy(a, 0, b, bn-i, i, itemSize);
                    memcpy(a, maxItems-an-i, a, maxItems-an, an, 4);
                    memcpy(a, maxItems-i, b, maxItems-bn, i, 4);
                    if (height != 1) { 
                        memcpy(a, i-1, pg, r-1, 1, itemSize);
                    }
                    memcpy(pg, r-1, b, bn-i-1, 1, itemSize);
                    setnItems(b, getnItems(b) - i);
                    setnItems(a, getnItems(a) + i);
                    db.pool.unfix(a);
                    db.pool.unfix(b);
                    return Btree.op_done;
                } else { // merge page b to a
                    memcpy(a, bn, a, 0, an, itemSize);
                    memcpy(a, 0, b, 0, bn, itemSize);
                    memcpy(a, maxItems-an-bn, a, maxItems-an, an, 4);
                    memcpy(a, maxItems-bn, b, maxItems-bn, bn, 4);
                    if (height != 1) { 
                        memcpy(a, bn-1, pg, r-1, 1, itemSize);
                    }
                    db.freePage(getReference(pg, maxItems-r));
                    setReference(pg, maxItems-r, getReference(pg, maxItems-r-1));
                    setnItems(a, getnItems(a) + bn);
                    setnItems(pg, nItems - 1);
                    db.pool.unfix(a);
                    db.pool.unfix(b);
                    return nItems*(itemSize + 4) < keySpace/3
                        ? Btree.op_underflow : Btree.op_done;
                }
            }
        }
    }