Извличане на документи и инвертирани индекси
-
за целите на web приложенията
Следните видове заявки:
-
документа се разглежда като кортеж, т.е. големи полета. При едно такова разглеждане може да има твърде много атрибути (за всяка дума да има по един атрибут [булев, т.е. дали дадената дума я има или не]). Върху всеки от тези атрибути се изгражда вторичен индекс (само за тези кортежи, в които стойността на атрибута е true).DOC (has Cat, has Dog, …) Вместо да се създават отделни индекси за всеки атрибут индексите са инвертирани в един, а именно инвертиран. Този индекс се пренасочва за да се спести дисково пространство
cat
|
|
dog
|
dog
|
- инвертиран индекс ; - списъци с адреси ; - отделни документи
Самите документи могат да бъдат разположени в поредица от блокове, т.е. да са част от базата от данни. Някои бази от данни са статични – няма смисъл от блокове на препълване, достатъчно е да се остави 25% празно място.
-
указателите могат да бъдат указатели към самия документ, но могат да бъдат и указатели които да сочат вътре в самите документи (къде точно се среща думата).
-
когато се ползват указатели към думи се ползва допълнителна информация към всяка една поява (дали се среща в заглавие или подзаглавие или в основния текст)л във връзка с появата на документи които се маркирани във файла с кофите съдържа информация с кой език за маркиране е създаден
|
Тип на маркировката
|
Позиция
|
Самия указател
|
cat
|
title
|
5
|
Doc1
|
|
header
|
10
|
|
|
anchor
|
3
|
Doc2
|
|
text
|
57
|
Doc3
|
dog
|
title
|
100
|
Doc2
|
|
title
|
12
|
Doc3
|
речника
|
маркери
|
|
|
Инвертирания индекс е речника, списъка с адресите са индексните файлове, това е при ПТБД.
Заявка1: да изкара всички документи, в които заглавието съдържа dog
Заявка2: да се намерят всички документи, в които в елемента title или в някои негови под-елементи се съдържа думата cat.
За заявка2 се използва XQuery - език, който прилича на SQL за СУБД.
По отношение на думите се използват най-различни методи:
-
търсене по корен на думите – суфикс;
-
стоп думи (по кои да не се индексира);
-
организацията – хубаво е в отделни блокове да се съдържат индексите за дадена дума.
Аспекти на XML
-
XML – ефективно средство за обмен на форматирана релация, заедно с това схемата на този файл върви (DTD+ XML-Scheme-по-точна информация).
-
Освен това XML е за съхраняване на документи (форматиране на документи) при ПТБД – XQuery. Към релацията в СУБД могат да се направят XML интерфейси.
-
XML е и средство, което служи за описание на семантиката на данните, т.е. данните идват като съдържание и това комбинирано с каскадните стилове и средствата за визуализация то те се визуализират.
Б – дървета
Тези индекси, които до сега разглеждахме се използват на едно-две нива, които ускоряват бързодействието. Но в съвременните СУБД се използват В – дървета. В – дърветата са една фамилия от данни. Най-характерно за тях е, че те поддържат толкова нива на индексация, колкото е необходимо отчитайки размера на дадения файл. Те управляват заетостта на блоковете си така, че поне на половината да са пълни. В – дървото организира блоковете си във вид на дърво, а В означава балансирано (Balanced). Има три вида нива в В-дървото:
-
Корен
-
Междинно ниво (може да са повече от едно)
-
Листа (едно ниво).
С всеки индекс на дървото е свързан параметър n, който определя структурата на блока, т.е. в един блок има n стойности и n+1 указателя. И е толкова голям, че да се вместят n ключа и n+1 указателя. Ключовете най-често са с фиксирана дължина. Съдържание на блоковете на В-дърветата:
-
ключовете в листата са копие на ключовете във файла с данни. На нивото на листата ключовете се поддържат в сортиран ред от ляво на дясно (в ляво – най-малката стойност).
-
в корена има поне два използвани указателя, като всички указатели сочат в блокове от по-долното ниво (но има случаи и само с един използван указател [1корен-1листо]). Указател от корена към листото и от листото към записа с данни
-
в листата последния указател сочи към следващия блок към листото намиращо се в дясно (т.е. сочи винаги в следващия блок с листа, там се намират листата с по-големи ключове от ключовете на разглеждания блок). Останалите указатели сочат в записи с данни и като бройка са , т.е. листата са поне наполовина пълни (в В+ дървото).
-
в междинните възли всички указатели (n+1) сочат към по-долното ниво.в тях има поне указатели (отново междинните блокове да са наполовина пълни). Тук спрямо ключа двата съседни указателя сочат:
указателя в ляво от ключа сочи в В-дървото, където се намират всички записи с ключове по-малки от разглеждания, а десния – в частта от В-дървото, в която са по-големи или равни от разглеждания ключ. Ако разглеждаме един блок в който това означава, че в блока ще има 4 указателя и в блока ще има 3 ключа
57
|
81
|
95
| листо към следващия блок с листа
запис с ключ 57 запис с ключ 81 запис с ключ 95
57
|
81
|
| листо към следващия блок с листа
запис с ключ 57 запис с ключ 81
междинен възел - най-малко 2 ключа
57
|
81
|
95
| Стойности по-големи от 95
Всички записи Ключове със Стойности между
с ключ по-малък стойности между 81 и 95
от 57 57 и 81
В-дървото извършва търсене в интервални заявки.
Използване на В-дървета
Инструментариум за изграждане на индекси (нивата се изграждат автоматично)
-
указателите – може ключа на търсене да е първичния ключ на релацията, а самия индекс да е плътен, т.е. една двойка ключ-указател, тогава не е необходимо файла с данните да е сортиран, защото листата са сортирани.
-
Но ако файла с данните е сортиран тогава можем да използваме разреден индекс. Тогава в дървото ще участват най-малките ключове от съответните блокове от файла с данни.
-
Когато файла с данни е сортиран по атрибут който не е ключ на релацията, но този ключ се използва за ключ на търсене (или ключ на индексация) в В-дървото тогава възможностите са:
В-дървото може да бъде и плътен и разреден индекс. Има В-дървета, които поддържат дублиране на ключове, представя се със схема аналогична на разширените индекси (променя се смисъла на дефиницията в междинните възли – ако в един междинен възел има ключове тогава е най-малкия нов ключ, който се появява в частта от дървото намиращо се в която сочи i+1 указател. В корена определението е същото)
Сподели с приятели: |