Grid съхранява голям обем данни (терабайтове)

1100 j = i =1

0000

1100 2

0001 2

1010 2

0001

1100 3

• 
  най – важно преимущество на линейните хеш таблици е че никога не търсим в повече от един блок;
  
• 
  масива с указатели е буфериран в оперативната памет, т.е. достъпи до него не се извършват, а достъпите са до блоковете в които сочат указателите;
  

• 
  когато се удвоява размера на масива на кофите при голямо i трябва да се извърши доста работа, т.е. достъпа до файла се прекратява сравнително продължително, или някои вмъквания на записи стават много по – бавно от други;
  
• 
  при удвояване на масива на указателите може той вече да не се побира в оперативната памет (използва много повече дискови операции за извършване на заявките);
  
• 
  ако броя на записите в 1 блок е малък, то тогава по – вероятно е блока да се раздели предварително за да се печели време, защото може да се стигне до такъв абсурд, че да се използват 20 бита за три записа;
  
• 
  най – съществен недостатък е нарастването на масива, поради тази причина се използва линейното хеширане, което също увеличава, но много по – слабо;
  

ЛИНЕЙНО ХЕШИРАНЕ

- броя на кофите n винаги се избира така, че запълнеността в дадена кофа да е 80 %;

- допускат се и блокове на препълване (по един блок);

! В най - лошия случай – три дискови достъпа.

- броя битове, които се използват за номериране на елементите е | log ₂ n |, където n е броя кофи;

Имаме запис с ключ k, този запис се изчислява с помощта на функцията h(k), и това е някакво число m, което представено двоично изглежда така:

m = а₁, а₂, …а_i ;

n – текущия брой кофи;

Ако m < n => означава, че съществува кофа, в която може да се запише записа;

Но ако n ≤ m < 2ⁱ => означава, че няма кофа, в която може да бъде вмъкнат този запис – тогава трябва да създадем съответната кофа. Този запис трябва да бъде поставен в кофа m – 2^{i – 1}, т.е. ние трябва да го поставим в кофата в която а₁ го заменим с 0 (а₁ задължително е 1);
m = а₁, а₂, …а_i ;

∕∕

0

1010

Но ако m ≥ n, тогава се опитваме да поставим в m – 2^{i – 1}, т.е. а₁ – (най-старшия) го превръщаме в нула, но може да се случи, че и там не можем да го вмъкнем, и тогава съществува блок на препълване, който го закачаме към m^–та кофа. При вмъкване обаче (независимо как сме го извършили) винаги правим проверка какво става със запълването и ако сме надхвърлили средното запълване – тогава добавяме само една кофа и в тази кофа ние разделяме кофата, която е била с

и тези записи ще ги разделим между нея и ново-добавената кофа.

Ако n превиши 2ⁱ – тогава i се увеличава с 1, което означава, че всички останали получават по една нула отпред, а поредицата от битове става с 1 повече.

Пример:

0101
Но това вмъкване надвишава 85 %, т.е. = 2 > 1,7

0101

↓ в 0 и гледаме в коя кофа ще попадне

1111 0001

0101

1010

0001

0111 → нова кофа и от 01

Всъщност се прилагат динамичните хешове, а не линейните.

Многомерни и побитови индекси – използват се за решетъчни файлове, разпределени хеш функции.