*         it follows the last key in the page.
     * @throws PersistitInterruptedException
     */
    int findKey(Key key) throws PersistitInterruptedException {
        final FastIndex fastIndex = getFastIndex();
        byte[] kbytes = key.getEncodedBytes();
        int klength = key.getEncodedSize();
        int depth = 0;
        int left = KEY_BLOCK_START;
        int right = _keyBlockEnd;
        int start = left;
        int tailHeaderSize = _tailHeaderSize;

        for (int p = start; p < right;) {
            //
            // Here we MUST land on a KeyBlock at an ebc value change point.
            //
            int kbData = getInt(p);
            int index = (p - start) >> 2;
            int runCount = fastIndex.getRunCount(index);
            int ebc = decodeKeyBlockEbc(kbData);

            if (depth < ebc) {
                // We know that depth < ebc for a bunch of KeyBlocks - we
                // can skip them. We can skip all KeyBlocks with ebc values
                // equal to or greater than this one, so whether there's a
                // runCount (positive) or crossCount (negative), we skip
                // this KeyBlock and all its successors.
                if (runCount < 0) {
                    runCount = -runCount;
                }
                p += KEYBLOCK_LENGTH * (runCount + 1);
                continue;
            }

            else if (depth > ebc) {
                int result = p | (depth << DEPTH_SHIFT);
                return result;
            }

            else // if (depth == ebc)
            {
                // Now we are looking for the keyblock with the matching db
                int db = decodeKeyBlockDb(kbData);
                int kb = kbytes[depth] & 0xFF;

                if (kb < db) {
                    int result = p | (depth << DEPTH_SHIFT);
                    return result;
                }
                if (kb > db) {
                    if (runCount > 0) {
                        //
                        // There is a run of runCount keys after p that all have
                        // the same ebc. Depending on how big the run is, we
                        // either do a linear search or perform a binary search
                        // within the run.
                        //
                        int p2 = p + (runCount * KEYBLOCK_LENGTH);
                        //
                        // p2 now points to the last key block with the same
                        // ebc in this run.
                        //
                        int kbData2 = getInt(p2);
                        int db2 = decodeKeyBlockDb(kbData2);
                        //
                        // For the common case that runCount == 1, we avoid
                        // setting up the binary search loop. Instead, the
                        // result is completely determined here by the
                        // value of db2.
                        //
                        if (runCount == 1) {
                            if (db2 > kb) {
                                //
                                // This is right because we already know
                                // that kb > db.
                                //
                                int result = p2 | (depth << DEPTH_SHIFT);
                                return result;
                            } else if (db2 < kb) {
                                //
                                // The key at the end of the run is still less
                                // than kb so we just skip the entire run and
                                // increment p. One possibility is that the
                                // run is interrupted by a series of deeper keys
                                // -
                                // in that case we use the cross count to skip
                                // all of them.
                                int runCount2 = fastIndex.getRunCount(index + runCount);
                                assert runCount2 <= 0;
                                p = p2 + KEYBLOCK_LENGTH * (-runCount + 1);
                                continue;
                            } else {
                                //
                                // Found it right here. We'll fall through to
                                // the equality check below.
                                //
                                p = p2;
                                db = db2;
                            }
                        }
                        //
                        // If runCount > 1 then we have more work to do.
                        //
                        else if (db2 > kb) {
                            //
                            // The key block we want is between [p, p2).
                            // Time to do a binary search.
                            //
                            left = p;
                            right = p2;
                            //
                            // Adjust left and right bounds of the range
                            // using db - kb difference; every db must differ
                            // from its predecessor because the ebcs are all
                            // the same. Therefore the we can define upper
                            // bounds on the maximum distance from the left
                            // and right ends of the range to the keyblock
                            // we are seeking.
                            //
                            if (runCount > BINARY_SEARCH_THRESHOLD) {
                                int distance = (right - left) >> 2;
                                int oldRight = right;
                                if (distance > kb - db + 1) {
                                    right = left + ((kb - db + 1) << 2);
                                }
                                if (distance > db2 - kb + 1) {
                                    left = oldRight - ((db2 - kb + 1) << 2);
                                }
                            }
                            //
                            // Perform binary search
                            //
                            while (right > left) {
                                p = ((left + right) >> 1) & P_MASK;
                                if (p == left) {
                                    //
                                    // This is true because if p == left then
                                    // right must be left + 1. We already know
                                    // that kb > db and less than db2, so the
                                    // final answer is know to be in right.
                                    //
                                    int result = right | (depth << DEPTH_SHIFT);
                                    return result;
                                }
                                //
                                // Otherwise perform a probe and the current
                                // mid-point and
                                // adjust the ends depending on the comparison.
                                //
                                int db1 = getDb(p);

                                if (db1 == kb) {
                                    db = db1;
                                    break;
                                } else if (db1 > kb) {
                                    right = p;
                                } else {
                                    left = p;
                                    db = db1;
                                }
                            }
                        } else if (db2 < kb) {
                            //
                            // We just want to move forward from kb2, skipping
                            // the crossCount if non-zero.
                            //
                            index = (p2 - start) >> 2;
                            runCount = fastIndex.getRunCount(index);
                            assert runCount <= 0;
                            p = p2 + KEYBLOCK_LENGTH * (-runCount + 1);
                            continue;
                        } else {
                            // found it right here. We'll fall through to the
                            // equality check below.
                            p = p2;
                            db = db2;
                        }
                    } else {
                        //
                        // Skipping all the keys in the crossCount. These keys
                        // are all deeper and therefore all fall before the db
                        // are looking for. This case also handles
                        // runCount == 0 where we simply advance to the next key
                        // block.
                        //
                        p += KEYBLOCK_LENGTH * (-runCount + 1);
                        continue;
                    }
                }

                assert db == kb;
                //
                // kb == db so we now try to go deeper into the key. On
                // an exact match we will perform this block of code once
                // for each byte in the key.
                //
                kbData = getInt(p);
                int tail = decodeKeyBlockTail(kbData);
                int tbData = getInt(tail);
                int tlength = decodeTailBlockKLength(tbData) + depth + 1;
                int qlength = tlength < klength ? tlength : klength;
                //
                // Walk down the key, increasing depth
                //
                boolean matched = true;
                if (++depth < qlength) {
                    int q = tail + tailHeaderSize;
                    kb = kbytes[depth];
                    db = _bytes[q++];

                    while (kb == db && ++depth < qlength) {
                        kb = kbytes[depth];
                        db = _bytes[q++];
                    }

                    if (kb != db) {
                        kb = kb & 0xFF;
                        db = db & 0xFF;

                        if (kb < db) {
                            //
                            // Key is less than tail, so we return
                            // this keyblock
                            //
                            int result = p | (depth << DEPTH_SHIFT) | FIXUP_MASK;
                            return result;
                        }
                        matched = false;
                    }
                }

                if (matched && depth == qlength) {
                    // We matched all the way to the end of either key or
                    // tail.
                    //
                    if (qlength == tlength) {
                        //
                        // We matched all the way to the end of the tail
                        //
                        if (qlength == klength) {
                            //
                            // And the key lengths are equal so this is an
                            // exact match.
                            //
                            int result = p | (depth << DEPTH_SHIFT) | EXACT_MASK;
                            return result;
                        }
                    } else if (tlength > qlength) {
                        //
                        // Tail is longer, so the key
                        // key is less than tail, so we return the
                        // this keyblock since it is greater than the key
                        //
                        int result = p | (depth << DEPTH_SHIFT) | FIXUP_MASK;
                        return result;
                    }
                    // Otherwise, the key is longer, so we move to the next
                    // key block at the bottom of this loop.
                }
                // Advance to the next keyblock
                p += KEYBLOCK_LENGTH;
            }

        }

        int result = right | (depth << DEPTH_SHIFT);
        return result;
    }