Индекстік файлдар жазбаны бірегей тҥрде анықтайтын бастапқы
кілттер ҥшін жасалғандықтан, онда оларда бірінші кілттің бірдей
мағынасы ие екі жазбалар болмайды. Негізгі саладағы əрбір жазбаның
тығыз индексі бар индекс файлдарында индекс саласынан бір жазба
бар. Индекс саласындағы барлық жазбалар кілттің мағынасы бойынша
реттеледі, сондықтан реттелген кеңістікте іздестірудің барынша тиімді
əдістерін қолдануға болады.
Еркін жазбаға қол жеткізудің ҧзақтығы абсолютті мағыналармен
бағаланбайды, əдетте дискі болып табылатын сыртқы жад
қондырғысына өтініштер саны бойынша бағаланады. Дискіге өтініш
шҧғыл жадыдағы барлық өңдеулермен салыстырғанда барынша ҧзақ
операциялар болып табылады.
Реттелген алаптағы барынша тиімді іздестіру алгоритмі
логарифмдік
немесе
бинарлық
іздестіру
болып
табылады.
Ықтималдылық теориясында ол жартылай бөліну əдісі деп аталады.
Осы əдістің пайда болуы артиллериялық ату теориясына байланысты.
Нысанаға жету ҥшін, нысана орналасқан барлық кеңістік екіге бөлінеді.
Содан кейін атыс объектінің орналасуы болжанған жартысында
жҥргізіледі. Снарядтың тҥсу нҥктесін белгілейді. Егер асып кетсе, онда
тҥзету жасалады – снарядтың тҥсу нҥктесі мен кесіндінің жартысы
арасындағы сала қайтадан екі бөлікке бөлінеді жəне тағы атады.
Бҧл жағдайда іздестіру қадамының жоғары саны (нысанаға дəл
тию) іздестіру кеңістігіндегі элементтердің (нысаналардың) жалпы
санының қосарлы логарифмімен анықталады:
T
n
= log
2
N,
(3.1)
мҧндағы N — элементтер саны.
Жазбаларды іздеген кезде бірінші кілттің берілген мағына бойынша
дискіге орналастыру саны ғана маңызды болып табылады. Алдымен
индекстік жазбаны іздестірудің қосарлы алгоритмі қолданылатын
индекстік салада іздестіру жҥргізіледі, ал содан кейін негізгі салада
іздеутікелей адрестеу арқылы жазбаның нөмірі бойынша іздестіру
жҥргізіледі. Жазбаға кірудің максималды уақытын бағалау ҥшін,
іздестіру ҥдерісінде дискіге өтініштер санын анықтау қажет.
Формулаға сəйкес (3.1) жазбаны іздестіру кезінде дискіге өтініштер
саны келесі жолмен анықталады:
T
n
=log
2
·N
инд. обл
+ 1,
мҧндағы N
инд.обл
— барлық жазбалар орналастырылатын индексті
блоктар саны.
Индексті блоктағы жазбаны іздестіруден кейін негізгі салаға тағы
жҥгіну қажет екенін ескере отырып, формулаға бірлік қосылды (+ 1).
Тығыз индексті файлды ұйымдастыру сұлбасы
Блок
Кілттер
Жазбаның
№ сілтеме
Еркін аймақ
салалар
1блок 01-10/01
3
И
нд
екс
ті
сал
а
02-20/02
4
03-20/00
5
2блок 06-40/00
7
07-50/01
8
08-30/01
9
3блок 10-44/01
1
11-44/02
2
09-35/01
6
4блок 17-20/03
10
18-40/02
11
20-35/02
12
Жазбаны
ң нөмірі
Кілт
Мазмҧны
Н
егі
згі
са
ла
1
10-44/01 Математика
2
11-44/02 Физика
3
01-10/01 Информатика
4
02-20/02 Ақпарат теориясы
5
03-20/00 дерекқор
6
09-35/01 АСО жəне У интерфейстері
7
06-40/00 Ақпаратты қорғау
8
07-50/01 АСТПП жəне АЖЖ
9
08-30/01 Бағдарламалау тілі
10
17-20/03 Операциялық жҥйелер
11
18-40/02 Интегралды қызмет көрсетудің
цифрлық желілері
12
20-35/02 Бағдарламалау технологиялары
Тығыз индексі бар файлдардағы жаңа жазбаларды қосу жəне жою
операцияларының қалай жасалатынын қарастырайық. 3.1-кестеде
дискілік кеңістікте осындай файлды ҧйымдастырудың сҧлбасы (еркін
аймақтар фонмен бөлінген) берілген.
3.1-кестеде көрсетілгендей, файл екі сала тҥрінде: негізгі жəне
индекс
ҧйымдастырылады. Негізгі
салада шешуші
өрістер,
жазбалардың сандары мен мазмҧны сақталады. Индекс саласында
шешуші өрістердің мəндері жəне негізгі саладағы жазбалар санына
сілтемелер сақталады.
Қосу операциясы кезінде деректер негізгі саланың шетіне жазу
жҥзеге асырылады. Бҧл ретте, индексті салаға тиісті шешуші өрістің
мағыналары мен жазбаның нөміріне сілтеме қосылуы керек, мҧнда
ақпарат жазбалардың тəртібі бҧзылмайтын етіп қосылуы тиіс.
Сондықтан да, файлдың барлық индекс саласы блоктарға бөлінеді жəне
əрбір блокта бастапқы толтырумен бос аймақ (кеңістік) жасалады.
Тиісті блоктың тиісті бос кеңістігінде қосымша жазба туралы ақпарат
енгізіледі.
Индексті саланы ҧйымдастырудың осындай тəсілі, əрбір деңгейде
бҧйымның қасиетін сипаттау ҥшін сандық санаттардың барынша ірі
саны қаралатын, ЕСКД жҥйелерінде көпдеңгейлі жіктеу (əріптік-
сандық кодтау) жҥйелеріне ҧқсас. Ол жҥйенің қателігінсіз өнімнің жаңа
тҥрлерін енгізу жəне оларға тиісті əріптік-сандық кодтары беруге
мҥмкіндік береді.
Сондықтан да, деректерді сақтаудың физикалық моделін жобалау
кезінде сақталатын ақпараттың көлемін нақыт анықтау, оның өсуін
болжау жəне соған сəйкес сақтау саласындағы тиісті кеңейтуді
қамтамасыз етуге болады.
Тығыз индексті файлдар тҥрінде деректерді сақтауды ҧйымдастыру
кезінде дискіге өтініштер саны формула бойынша жаңа жазбаны қосу
кезінде анықталады
T
n
=log
2
N
инд. обл
+ 1 + 1 + 1,
Формуланың мағынасы төмендегідей: өтініштер саны индекс
саласына жіберілген өтініштер санымен, оған негізгі блокқа қосылған
бір өтінішпен, индексті блокты өзгерту ҥшін бір өтінішті қосумен жəне
негізгі салаға жазба енгізу ҥшін бір өтінішті қосумен белгіленеді.
Осылайша, тығыз индексі бар файлдарда бір жазбаны өңдеу
кезінде компьютердің дискілік кеңістігіне екі қосымша өтінішті қажет
етеді.
Одан туындайтыны, дерекқор файлдарын ҧйымдастыру əдістері
жəне олардың тиісті физикалық ҥлгілері, оны іздестірген кезде дискілік
кеңістікке қол жеткізу уақытын қысқартуға жəне дерекқордың
мазмҧнын қосу жəне тҥзету уақытын қысқартуға бағытталуы тиіс.
Достарыңызбен бөлісу: |
