BD-2st-1.2-w06.tresc-1.1-Slajd37
Haszowanie zewnętrzne - kolizja
W haszowaniu zewnętrznym kolizje występują rzadziej niż w omawianej wcześniej technice haszowania wewnętrznego. Dzieje się tak dla tego, że ten sam LOD, którego numer jest wynikiem działania funkcji haszowej, może pomieścić wiele rekordów. Kolizja może jednak wystąpić po zapełnieniu się wszystkich bloków dyskowych wchodzących w skład danego LOD. W takiej sytuacji, alokowany jest obszar nadmiarowy. LOD zawiera wskaźnik do pierwszego rekordu tego obszaru. Kolejny rekord ulegający kolizji w tym samym LOD będzie zapisany w obszarze nadmiarowym, a wskaźnik do tego rekordu znajdzie się w poprzednim rekordzie obszaru nadmiarowego. Koncepcję tę ilustruje slajd.
LOD0 został w całości zapełniony rekordami 1 do l. Kolejny rekord m powinien trafić do LOD0. Z braku miejsca jest on umieszczany w obszarze nadmiarowym. W LOD0 jest umieszczany wskaźnik do tego rekordu. Następnie rekord m+1 również powinien trafić do LOD0 i jest umieszczany w obszarze nadmiarowym. Do rekordu m+1 prowadzi wskaźnik z rekordu m.
