public void insertElement(IndexPair pair) throws IOException {
    // If there is no block yet, allocate one and insert the element.
    if (firstBlock == null) {
      firstBlock = createNewBlock();
      firstBlock.insertElement(pair);
    } else {
      SignatureStoringBlock block = getBlockFor(pair.getBitSignature());
      if (block == null) {
        // If there is no block that might contain the pair, all blocks
        // have a greater start key.
        // So add to the first block.
        block = firstBlock;
      }
      if (block.getSize() < block.getCapacity()) {
        block.insertElement(pair);
      } else {
        // Split the block and add the elements:
        // 1. Create a new block and link it right after the current
        // block.
        SignatureStoringBlock newBlock = createNewBlock();
        newBlock.setPreviousBlock(block);
        newBlock.setNextBlock(block.getNextBlock());
        block.setNextBlock(newBlock);
        if (newBlock.getNextBlock() != null) {
          newBlock.getNextBlock().setPreviousBlock(newBlock);
        }

        // 2. Retrieve all elements and spread them over the new blocks.
        IndexPair[] pairs = block.getElements();
        int splitIndex = pairs.length / 2 + 1;
        block.bulkLoad(pairs, 0, splitIndex);
        newBlock.bulkLoad(pairs, splitIndex, pairs.length - splitIndex);

        // 3. Find the target block for the new element and add it.
        if (BitSignatureUtil.COMPARATOR.compare(pair.getBitSignature(),
            newBlock.getStartKey()) < 0) {
          block.insertElement(pair);
        } else {
          newBlock.insertElement(pair);
        }
      }
    }
  }