Поиск в БД через AJAX, Логика очередности выполнения

Всё что вам нужно сделать, это не забывать про созданный для поиска объект запроса, и для нового поиска, если запрос уже существует вызывать его прерывание (для jquery тоже можно var rq = $.ajax(...); rq.abort();).

1 вариант - запрещать ввод в поле пока не завершится запрос. Тут либо добавить readonly, либо может быть поверх невидимый блок положить, и не забыть focus снять с поля.

2 вариант - кроме запрета выполнения запросов пока предыдущий не закончился добавить ожидание, например делать запрос когда человек 1 секунду ничего не вводил.

var timeout;
$('input').on('keyup', function(){
  clearTimeout(timeout);
  timeout = setTimeout(function(){
    request();
  });
});

3 вариант - хранить признак того, что надо сделать еще один запрос на случай, если человек что-то вводил пока выполнялся текущий запрос

var lateRequest = false,
    requestProcess = false;
$('input').on('keyup', function(){
  if (requestProcess) {
    lateRequest = true;
  } else {
    request();
  }
});
function request() {
  requestProcess = true;
  $.ajax({
    complete: function(){
      // обработка ответа...
      if (lateRequest) {
        lateRequest = false;
        request();
      } else {
        requestProcess = false;
      }
    }
  });
}

Только тут надо будет еще проверить ситуации, когда запросы могут слаться бесконечно один за одним))

Ну и можно совместить все три варианта

P.S. 4 вариант - добавить кнопку submit =)