Двоичното търсене се основава на разделянето на дадено множество от записи на две равни части, сравняване на търсения идентификатор с последния запис от горната половина или с първия запис от долната половина и установяване по този начин в коя половина се намира той. Следва търсене в така откритата половина чрез нейното разделяне на две части и така нататък докато се стигне до желания запис. По този начин се намалява броят на четенията на записи и се спестява време от тази най-времеемка компютърна операция. Според теория на вероятностите при брой на записите n и последователно търсене средновероятният брой на четенията и свързаните с тях сравнения е n/2. При двоично търсене този брой е значително по-малък.
Блочно търсене
Блочното търсене е подобно на двоичното. Но деленето на файла става не на две равни части, а на блокове с еднакъв брой записи във всеки. Блок след блок се прави четене и проверка на последния запис докато се открие блокът, в който е търсеният запис. След това така намереният блок се чете последователно докато се намери в него търсеният запис. Всичко това означава, че броят на четенията зависи не само от общия брой записи, но и от големината на блока. Средният вероятен брой на четенията тук е по-голям от броя на четенията при двоичното търсене, нопо-малък от този при последователно четене.
Индексиране
Най-използваният метод за бързо намитане на даден запис в настоящия момент е индексирането. При него освен основният файл се създава и използва допълнителен, индексен файл. Индексният файл съдържа сортирани главните ключове, придружени от адресите, на които се намират записите им в основния файл. Обикновено индексният файл е организиран за бързо търсене по главен ключ чрез метода на двоичното или блочното търсене. След като е открит адресът на търсения запис в индексния файл се отива по него в съответния запис от основния файл. Ускоряванетo тук е за сметка на по-бързото двоично търсене в индексния файл в сравнение с двоично търсене в основния файл. Записите в индексния файл са къси и той целият може да се прегледа в бързата оперативна памет. Записите в основния файл са дълги, той не се събира в оперативната памет и двоичното търсене в него е по-дълго. Индексни файлове могат да се организират и за групови ключове, като в този случай за един групов ключ в индексния файл се записват много адреси – адресите на всички записи, които имат този групов ключ. Тук неудобството е, че за различните групови ключове броят на притежаващите ги записи е различен. Това води до запазване на място в индексния файл за групата с най-голям брой записи и естествено до празни полета в много от записите на индексния файл и до разход на памет.
___________
ИЗ “РАБОТА С БАЗИ ОТ ДАННИ”
в примери на ACCESS 2003 – 2007
със SQL, VBA и ADO
© Румяна Цанкова
© Владимир Л. Станчев
Под редакцията на проф. д.т.н. Румяна Цанкова
Корица и оформление Владимир Л. Станчев
Рецензент доц. д-р инж. Светослав Димков Велев
МП Издателство на Технически университет – София
София, 2007
Сходни статии:
- Интелигентна система за демонстриране методи за търсене в пространствено състояниe Графа може да се опише чрез отношението ”nasl”. Съседството между два възела X и Y може да се изрази чрез предиката: nasl(X,Y). който е в сила,ако Y е непосредствен...
- Копиране и преместване на компресирани файлове При копиране и преместване атрибутите за компресиране на файловете, разположени в NTFS дял, могат да се променят. Копиране При копирането на файл от една папка в друга неговият атрибут за...
- Релации и връзки между таблици Същност на релациите. След като данните са въведени в таблиците, следва да се укаже как програмата да ги свърже, за да може впоследствие да се създават заявки, форми и справки,...
- SEO оптимизация за търсене по изображение SEO оптимизацията за търсачки по изображение е процес на организиране на съдържанието на уеб страница, така че да повиши връзката между специфичните ключови думи на търсачките, които използват изображения. Също,...
- Оптични носители – CD устройства Принцип на действие на оптично дисково устройство. Данните се съхраняват по протежение на единичен спирален път с дължина обикновено 40 000 оборота. Пътечките са разделени на сектори, всеки от които...
