mySQL и int'овый несоставной pk

:D Такое вот дело. Есть около 8-10 таблиц, для каждой, кроме одной задано по одному простому pk int(11) unsigned. Auto-increment юзать не хочу, но требования у меня к этим pk те же. Вопрос такой: как бы более правильно и экономно по части ресурсов искать свободные значения pk делая вставки, если потолок уже забит и MAX'ом не воспользуешься. Или другой вариант: как добиться такого же механизма работы для pk, как у auto_increment'а по составному пк (где при вставках заполняется первое свободное значение, а не max+1).

Все что опробывал жрало слишком много ресурсов и слишком долго выполнялось. :/ Есть какие варианты?