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

1. 
   Търсене на близък блок. Може да се използват и прехвърлящи адреси (в таблицата на офсетите са слага указател като се намери празно място и указателя има прехвърлящ адрес към блока, къде е поставен).
   
2. 
   Създаване на блок на препълване – във всеки блок имаме верига (блок) на препълване
   

Във времето данните се изменят, еволюират (чрез вмъкване, изтриване и т.н.). Данните за представянето също трябва да се изменят – при напълването на блока данните трябва да се преместят и регистрират. Създават се блокове на препълване при необходимост от допълнително пространство и се изтриват когато се изпразнят. При тази техника характерното за индекса е че не поддържа индекс за блоковете на препълване – само блок, който е разширен с блоковете на препълване. Другия подход е вместо да използваме блок на препълване вмъкване на нови блокове в последователната наредба, но това означава, че в индексния файл трябва да вмъкнем елемент чрез който да се индексира този нов блок. Вмъкването на този нов елемент в индекса може да породи същите проблеми като при вмъкване на нов елемент. Използва се и когато се вмъкне даден кортеж в блока, но няма място се търси място в съседните блокове. Тази техника се комбинира – когато съседните блокове станат “рехави”. Можем да ги комбинираме, освобождавайки някои блок. Настъпилите изменения трябва да се отразят в индекса. Независимо коя стратегия се използва силно зависи как ще действаме от вида на индекса – плътен или разреден. Индексния файл може да се разглежда като последователен файл. За него може да прилагаме същите три стратегии.

Действие Плътен индексРазреден индексСъздаване на празен блок на препълванеНе се прави нищоНе се прави нищоИзтриване на празен блок на препълванеНищо Нищо Създаване на празен последователен блокНищо Операция по вмъкване, индексираща този блокИзтриване на празен последователен блокНищо Изтриване на елементаВмъкване на записВмъкване на запис в индексаМоже да има обновяване (ако записът е с най-малък ключ)Изтриване на записИзтриване на двойката указател-блокМоже да има обновяванеПреместване на записОбновяване Може да има обновяване ако новия блок не съдържа по-малки ключове

Когато подготвяме даден файл и индекси ги подготвяме за еволюция на данните: не запълваме блоковете при първоначалното зареждане. Средно ги запълваме до 75%. Това помага да се отложи във времето промените. Записите нарастват. По отношение на еволюцията на данните е добре да не трябва да се създават блокове на препълване. За предпочитане е да се прилага стратегия, в която да имаме празно пространство, а ако поддържаме блокове на препълване да няма повече от един.

Пример:

10

30

50

70

Ако изтрием запис с номер 30: в индекса изтриваме елемента за запис с номер 40 и го преместваме. Ако изтрития запис е прикован се слага надгробен камък

При разреден индекс:

30

5060изтриваме запис с номер 30 съответния елемент от 30 става 40

10

40

50

70

//////////

Ако изтрием и запис с номер 40 връзката се изтрива

10

Вмъкване

10

//////////

1. 
   вмъкваме запис с ключ 15
   

10

20

Защото заема само 1 бит

1. 
   чрез блок на препълване
   

10

//////

Основния файл е сортиран по индексния ключ. При вторичните индекси основния файл не е задължително да е сортиран по ключът на индекса. Първичния ключ е ключа, по който уникално се идентифицират кортежите. На физическо ниво вторичния ключ може де е различен от първичния. Най-често първичния и ключа на сортировка съвпадат. Ако не е така е правилно да сортираме релацията по този ключ, по който най-често се търси. Най-често става когато се ползват номенклатури. Вторичния индекс се пълни с много дубликати. Най-особената черта на вторичния индекс е, че той винаги е плътен. Нагоре в йерархията трябва да са разредени. Пример: при изграден вторичен индекс, записите са сортирани по ключ. Приложение на вторичен индекс: когато се създава вторичен индекс върху файлове от вида heap (един след друг; файлове, които не са сортирани). Клъстърен файл – в него се поддържат две релации в блоковете (една за филмите и за студията) studios - отношение 1 към много movies - операция-съединение

клъстърен файл

Studio1Film1Film2…Studio2Film1Film2…

10

10

20

50

10

50

60

Върху така организирания клъстърен файл се прилага вторичния индекс. Един индекс по студията и един по филмите. Първият индекс е организиран по атрибут/и на студията, а вторият – по атрибут/и на филмите. Те трябва да са плътни.

Трети подход – пренасочване при вторичните индекси. При пренасочването има преразход на памет. Смисъла е - би било хубаво индекса да участва само един път, а повторенията да са в отделна структура.

20

40

10

10

50

50

10

60

1. 
   помощна структура, нарича се файл с кофите (bucket) или с директориите.
   

SELECT title

FROM movie

WHERE StudioName=”Disney”

AND year=1995

…

1995

Извличане на документи и инвертирани индекси

1. 
   за целите на web приложенията
   

Следните видове заявки:

1. 
   документа се разглежда като кортеж, т.е. големи полета. При едно такова разглеждане може да има твърде много атрибути (за всяка дума да има по един атрибут [булев, т.е. дали дадената дума я има или не]). Върху всеки от тези атрибути се изгражда вторичен индекс (само за тези кортежи, в които стойността на атрибута е true).DOC (has Cat, has Dog, …) Вместо да се създават отделни индекси за всеки атрибут индексите са инвертирани в един, а именно инвертиран. Този индекс се пренасочва за да се спести дисково пространство
   

cat

cat

dog

- инвертиран индекс ; - списъци с адреси ; - отделни документи

Самите документи могат да бъдат разположени в поредица от блокове, т.е. да са част от базата от данни. Някои бази от данни са статични – няма смисъл от блокове на препълване, достатъчно е да се остави 25% празно място.

1. 
   указателите могат да бъдат указатели към самия документ, но могат да бъдат и указатели които да сочат вътре в самите документи (къде точно се среща думата).
   
2. 
   когато се ползват указатели към думи се ползва допълнителна информация към всяка една поява (дали се среща в заглавие или подзаглавие или в основния текст)л във връзка с появата на документи които се маркирани във файла с кофите съдържа информация с кой език за маркиране е създаден
   

Тип на маркировкатаПозиция Самия указателcattitle5Doc1header10anchor3 Doc2text57 Doc3dogtitle100 Doc2title12 Doc3речникамаркери

Заявка1: да изкара всички документи, в които заглавието съдържа dog

Заявка2: да се намерят всички документи, в които в елемента title или в някои негови под-елементи се съдържа думата cat.

За заявка2 се използва XQuery - език, който прилича на SQL за СУБД.

По отношение на думите се използват най-различни методи:

1. 
   търсене по корен на думите – суфикс;
   
2. 
   стоп думи (по кои да не се индексира);
   
3. 
   организацията – хубаво е в отделни блокове да се съдържат индексите за дадена дума.
   

Аспекти на XML

1. 
   XML – ефективно средство за обмен на форматирана релация, заедно с това схемата на този файл върви (DTD+ XML-Scheme-по-точна информация).
   
2. 
   Освен това XML е за съхраняване на документи (форматиране на документи) при ПТБД – XQuery. Към релацията в СУБД могат да се направят XML интерфейси.
   
3. 
   XML е и средство, което служи за описание на семантиката на данните, т.е. данните идват като съдържание и това комбинирано с каскадните стилове и средствата за визуализация то те се визуализират.
   

Б – дървета

1. 
   Корен
   
2. 
   Междинно ниво (може да са повече от едно)
   
3. 
   Листа (едно ниво).
   

1. 
   ключовете в листата са копие на ключовете във файла с данни. На нивото на листата ключовете се поддържат в сортиран ред от ляво на дясно (в ляво – най-малката стойност).
   
2. 
   в корена има поне два използвани указателя, като всички указатели сочат в блокове от по-долното ниво (но има случаи и само с един използван указател [1корен-1листо]). Указател от корена към листото и от листото към записа с данни
   
3. 
   в листата последния указател сочи към следващия блок към листото намиращо се в дясно (т.е. сочи винаги в следващия блок с листа, там се намират листата с по-големи ключове от ключовете на разглеждания блок). Останалите указатели сочат в записи с данни и като бройка са , т.е. листата са поне наполовина пълни (в В+ дървото).
   
4. 
   в междинните възли всички указатели (n+1) сочат към по-долното ниво.в тях има поне указатели (отново междинните блокове да са наполовина пълни). Тук спрямо ключа двата съседни указателя сочат:
   

запис с ключ 57 запис с ключ 81 запис с ключ 95

запис с ключ 57 запис с ключ 81

Всички записи Ключове със Стойности между

с ключ по-малък стойности между 81 и 95

от 57 57 и 81

В-дървото извършва търсене в интервални заявки.
Използване на В-дървета

Инструментариум за изграждане на индекси (нивата се изграждат автоматично)

• 
  указателите – може ключа на търсене да е първичния ключ на релацията, а самия индекс да е плътен, т.е. една двойка ключ-указател, тогава не е необходимо файла с данните да е сортиран, защото листата са сортирани.
  
• 
  Но ако файла с данните е сортиран тогава можем да използваме разреден индекс. Тогава в дървото ще участват най-малките ключове от съответните блокове от файла с данни.
  
• 
  Когато файла с данни е сортиран по атрибут който не е ключ на релацията, но този ключ се използва за ключ на търсене (или ключ на индексация) в В-дървото тогава възможностите са:
  

(при случаите, когато не се поддържат дубликати и индекса е плътен)

търсенето не се свежда само до търсене в индекса, но и в блока данни в основния файл. При дубликати – попадаме в листо и трябва да продължим в дясно по листата.

Търсенето в В-дървета се реализира индукционно – във вид на рекурсивна програма. В основата на този индукция е, че ако сме в листо търсим сред ключовете му, ако i-тия ключ е търсения ключ к, то i-я указател ще ни заведе в търсения запис (файла с данните, където е записан).

Индукция – намираме се в междинен възел с ключове k …k тук трябва да решим към кое от децата ще се насочим. Има само едно дете, което може да ни заведе към възела, съдържащ к. Ако k>k то първото дете на междинния възел ще ни насочи към възела, който съдържа ключа к. Ако k <=k използваме второто дете и т.н. Т.е. в случая k <=k избираме детето k . Процедурата се прилага рекурсивно.

13 k=40 k

k k k следваме третата връзка

233143

313741

43

1. 
   Интервални заявки (търси се по интервал). Ключът на търсене се сравнява (в WHERE) с дадена стойност/и (без “равно” и “различно”).
   

FROM R

При интервалните заявки имаме търсене по даден ключ в затворения интервал а,b – стартираме търсене по ключа а – стигаме до листото, където се намира а, тръгваме надясно и обхождаме всички листа по-малки от b. Ако всички са по-малки преминаваме в следващото листо и така до срещане на ключ, по-голям от b или до края на списъка на листата.

Пример:

131719

313741

Вмъкваме 40 – трябва да разделим третото листо .

233143

3137

4347

В по-горния ред няма място трябва да го разделим на две:

2331

43

3137

4347

И в корена:

4347

1343

Пример:

7

711

Изтриваме ключ с номер 7:

5

23

13

131719

За всяка операция, която те реализира са необходими много малки дискови операции. Необходимостта от реорганизация намалява при указатели и ключове 10 или повече. За повечето бази от данни няма повече от три нива на индексация в В-дървото. Необходими са не повече от пет дискови операции да се намери ключ. В някои В-дървета не се трие само се слага нулев указател. Повечето файлове обикновено растат.

“ХЕШ” ФАЙЛОВЕТЕ

Базират се на хеш таблици, като структури от данни в паметта. Имаме хеш функция, която се прилага върху ключа на търсене. Организацията се базира върху ключ на хеширане. Хеш функцията връща някаква стойност, която е в интервала 0 до В-1. “В” е броя на кофите, които съхраняват индексните стойности. Кофите също са индексирани от 0 до В-1. Използваме вторична памет за хеш таблиците.

Всяка една кофа е един блок. Във всеки блок се разполагат записите с една и съща стойност, т.е. ако “k” е ключ, то всички записи със стойност h(k) са разположени в един блок.

Кофата ако се препълни – тогава се слагат блокове на препълване.

нарича “масив на препълване”

указател за организиране на верига на препълване
0
1 нов блок
2

.

.

.
В-1

Особености:

При хеширането, идеалната хеш функция трябва равномерно да може да разпределя (ключовете) записите между отделните кофи.

Идеалния случай е на база на статистика, но обикновено не разполагаме с такова статистическо изследване.

- когато ключовете са цели числа - например символен низ:

- сумираме двойки символи

символен низ

1. Изчисляваме хеш функцията за този ключ

- ако в съответния блок има място – то го вмъкваме;

- ако няма място добавяме блок на препълване и поставяме записа;

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

- много висока ефективност – затова защото при търсене по ключ за да намери необходимия запис са необходими 1 или 2 дискови достъпа (в “В” дърветата са 3 достъпа, но тъй като то е в оперативната памет – достъпите се свеждат до два). В съвременните СУБД-та се използват хеш файлове.

- в хеш файловете не можем да сканираме в наредба; всички записи са разхвърляни съгласно хеш функцията. А повечето заявки са множествени заявки, а те налагат сканиране в интервал.
Тези таблици, които до сега разглеждахме се наричат статични, т.е. броя на кофите при реорганизация не се променя. Има и динамични.

Динамични хеш таблици:

1. Разширяемо хеширане – при установяване на препълване броя на кофите се удвоява;

2. Линейно хеширане – тук увеличението не е така драстично – увеличава се само с една кофа;

При разширяемо хеширане се прави просто допълнение към статичната хеш таблица, а именно:

- поддържа се едно допълнително ниво на пренасочване, т.е. използва се масив от указатели към блокове (този масив от указатели може да расте и винаги е степен на двойката) т.е. той се удвоява;

- не е необходимо всяка кофа да има блокове с данни, дори в определени случаи кофите могат да споделят блок (но само когато общия брой записи от двете кофи може да се събере само в един блок);

- хеш функцията за всеки един ключ пресмята една поредица от k на брой бита, като това k е достатъчно голямо (например 32 бита), обаче за номерация на кофите се използват само малка част от тези битове (например първите i бита от тази поредица);
Пример:

k = 4 (за всеки ключ ще ни върне 4 бита) и нека се използва само 1 бит за номерация на кофите, т.е. i = 1. Тогава хеш таблицата изглежда така:
масив от указатели

0001 1 = j

0

1 1001 1 = j

1001 1

↓

резултат от изчислението на хеш функцията,

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

1) ако има място – вмъкваме записа и приключваме;

2) ако няма място – нашите действия зависят от едно число j, което показва колко бита са използвани за определяне на принадлежността към блока;

- в І^-я блок всички записи в които в j + 1^-я бит има стойност 0;

- в ІІ^-я блок всички записи в които в j + 1^-я бит има стойност 1;

(в І^-я блок j си остава j )

(в ІІ^-я блок j става j + 1 )
Указателите към масива на кофите го обновяваме така, че в В и в новия блок да сочат в зависимост от j + 1^-я бит.

Разделянето на два блока не решава проблема щото може да се случи пак да нямаме празно място => тогава повтаряме тази процедура.

0001