Как правильно организовать сортировку элементов с сохранением в базе данных их позиций?

Question

[Mysterion]

Всем доброго времени суток. Не могу решить проблему с организацией сортировки на сайте. Вернее с ее правильным сохранением позиций элементов.
Использую UI Sortable, в методе update передаю ajax'ом скрипту новый index элемента и сохраняю его для этого элемента в базе данных.
Проблема заключается в том, что необходимо и новые элементы создавать, а какой индекс присваивать им?
Допустим, у нас есть элементы:

Элемент 1 (индекс 1)
Элемент 2 (индекс 2)
Элемент 3 (индекс 3)
Элемент 4 (индекс 4)

Какой индекс присвоить новому элементу? И что делать с элементами, у которых совпадают индексы? Ведь можно один элемент перенести на вторую позицию и другой тоже. Следовательно, они оба будут иметь индекс 2 и как правильно их сортировать?
А если назначить в качестве индекса количество всех элементов и прибавить единицу, то в последствии такие элементы могут некорректно сортироваться. Например, было 5 элементов, новый добавился с индексом 6. Два элемента удалили и добавили еще один. Новый добавляется с индексом 5. Встанет он перед последним, что неверно.

Вообще, интересно как бы вы реализовали у себя сортировку с сохранением. Или как реализовали, если уже реализовано?
Необходимо хранить все элементы отдельно с их индексами. Хранение отдельно массива с индексами элементов не подходит.

Answer 1

[Mysterion]

Добавил тег Laravel, так как на нем решение применил свое, и выкладываю:
Бэкенду отправляю список элементов так:

$(this).sortable('toArray', {attribute: 'data-id'})

А элементы выглядят так:

<ul id="#sortable">
    <li data-id="5">Item 1</li>
    <li data-id="6">Item 2</li>
    <li data-id="9">Item 3</li>
</ul>

5,6,9 - это ID элементов в базе данных.
В результате приходит на бэкенд это так:
[5,6,9]
Соответственно, ключ элемента является индексом
Обрабатываю так:

$elements = Elements::where('user_id',$user_id)->get();
foreach($request->input('sort') as $k => $v)
    $rules['sort.'.$k] = 'required|integer';
$validation = Validator::make($request->only('sort'), $rules);
if($validation->passes()) {
    foreach($elements as $k => $v) {
        $sort_id = array_search($v['id'], $request->input('sort'));
        if($sort_id && $v['sort'] != $sort_id) {
            $v['sort'] = $sort_id;
            $v->save();
        }
    }
} else {
    abort(400);
}

Answer 2

[AlikDex]

1) При использовании UISortable индексы не будут повторяться, если сериализовать массив элементов. Инструмент для этого у виджета есть.
2) Когда создаете новый элемент, первым этапом проверяете правильность пришедших данных, затем выдергиваете максимальный индекс из базы с учетом текущей ветки, если это дерево, потом добавляете в базу с этим индексом + 1. Запрос будет выглядеть примерно так:

SELECT MAX(`position`) FROM `my_table` WHERE `parent_id`=@current_parent -- @current_parent это ид текущего родителя. Если для хранения используется adjacency list, например.

Собственно и все.