Зачем нужен уникальный index, содержащий RecId?

[AndyD]

Цитата:

Сообщение от fed

Кстати, не следует забывать, что сортировка по RID (Ну или ключу кластерному), дает не только выигрыш при удалении, но и проигрыш при вставке. При отсутствии сортировки по RID, я могу новый ключ пристроить в любую подходящую страницу (ну скажем если у нас 10000 записей с данным ключем уже есть), в которой есть свободное место. А вот если бы у нас была сортировка по RID, то нам бы пришлось искать одну единственную страницу (что долго) и туда вставлять. При этом, если места в странице нету, то придется ее сплитить и перебалансировать дерево.
Ну а учитывая что ключи удаляются реже, чем вставляются...

А почему вставка должна замедлиться?
Давай рассмотрим процесс?

Сначала, вставку куда получится

У нас есть 10тыс. уже вставленных значений индекса.
По ключу, мы хватаем первую страницу, но она уже заполнена (допустим, на страницу влазиет по 300 строк).
Ладно, хватаем следующую. Опять облом.
И так повторяем, пока не дойдем до последней (или берем ее сразу? Но тогда, как заполнять незанятое место?).

Получается, для предложенных условий, дергаем 34 страницы + количество уровней - 1 ( и это я еще не учел возможный переход по страницам верхних уровней). В самом оптимистическом случае количество страниц равно количеству уровней


Теперь, вставка при отсортированном Heap RID (или кластерном ключе)

Ну, тут очевидно, что открыто будет ВСЕГДА одно и тоже количество страниц, равное количеству уровней.

Ну и где здесь преимущество первого варианта?


По поводу окончания места в странице нижнего уровня.

Я здесь не вижу принципиальной разницы для обоих случаев.
Добавление страниц будет затрагивать только предыдущий уровень (для сплита, возможно - еще добавляется следующая страница, которую надо обновить)

А для неупорядоченного расположения страниц, как раз таки, добавляется еще необходимость проверять все страницы одного уровня, что бы убедиться, что вставлять некуда, перед тем как добавлять новую.

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


Ну и еще одну мысль добавлю: неотсортированное дерево теряет свое основное свойство - сбалансированность. Ведь, для того, что бы найти вхождение конкретной записи - надо будет перелопатить в общем случае страниц значительно больше, чем уровень вложенности.