Еркін жазба іздестіру механизмін жəне хэштеудің осы
стратегиясына арналған жазбаны жоюды қарастырамыз.
Жазбаны іздестірген кезде алдымен оның хэш-функциясының
мағынасы есептеледі жəне негізгі салада орналасқан синонимдік
тізбектегі бірінші жазба оқылады. Егерде ізделіп отырған жазу
синонимдер тізбегіне бірінші сəйкес келмесе, онда іздестіру
синонимдер тізбегі бойынша қажетті жазба табылғанға дейін
ауыстырыла отырып жҥзеге асырылады. Іздестіру жылдамдығы
синонимдер тізбегінің ҧзындығына байланысты, сондықтан хэш-
функциясының
сапасы
синонимдер
тізбегінің
максималды
ҧзындығымен анықталады. Тізбектегі 10-нан артық синонимдердің
болуын жақсы нəтиже деп санауға болады.
Еркін жазбаны кетіргенде ең алдымен оның орналасқан орны
анықталады. Егер синонимдер тізбегіндегі бірінші жазба кетірілетін
болса, кетірілігеннен кейін синонимдер тізбегіндегі екінші (келесі)
жазба негізгі саладағы оның орнына орналастырылады; бҧл ретте
барлық көрсеткіштер (синонимдерге сілтемелер) сақталады.
Егер кетірілетін жазба синонимдер тізбегінің ортасында болатын
болса, онда көрсеткішті реттеу қажет: кетірілгеннен кейінгі жазбада,
тізбеде кетірілетін жазбада көрсеткіш орналастырылады. Егер осы
тізбектегі соңғы жазба болатын болса, онда көрсеткіштерді өзгерту
механизмі бірдей, яғни алдыңғы жазбаға бҧрын соңғы жазбада
сақталған тізбектегі келесі жазбаның жоқтығы белгісі қосылады.
Еркін ауыстыру әдісімен коллизияны шешу. Осы стратегия
кезінде файлдық кеңістік салаларға бөлінбейді, бірақ əрбір жазба ҥшін
екі көрсеткіш қосылады: синонимдер тізбегіндегі алдыңғы жазбаға
көрсеткіш жəне синонимдер тізбегіндегі келесі жазбаға көрсеткіш.
Тіисті сілтеменің болмауы арнайы белгімен, мысалы нөлмен
көрсетіледі. Әрбір жаңа жазба ҥшін хэш-функциясының мағынасы
есептеледі жəне аталған мекенжай бос болатын болса, онда жазба
берілген орынға тҥседі жəне синонимдер тізбегінде бірінші болады.
Егер хэш-функциясының алынған мағынасына сəйкес келетін
мекенжай бос болмаса, онда сілтеменің болуына қарай, аталған
мекенжайда орналасқан жазбаның синонимдер тізбегінде бірінші
болып табылатыны анықталады. Егер солай болса, онда жаңа жазба
бірінші бос кеңістікте орналастырылады жəне ол ҥшін оған сəйкес
сілтемелер орнатылады: ол синонимдер тізбегінде екінші болады, оған
бірінші жазба сілтеме жасайды,
ал ол бар болса, келесіге нҧсқайды.
Егер талап етілетін орынды алатын жазбалар синонимдер
тізбегіндегі бірінші болып табылмаса, онда ол орынды «заңсыз» алып
жатыр жəне «заңды меншік иесі» пайда болған кезде оны «шығарып
тастау», яғни жаңа орынға көшіру қажет. Ауыстыру механизмі файлға
енгізілген синонимі бар жаңа жазбаны енгізуге ҧқсас.
Осы жазба ҥшін бірінші бос орын іздестіріледі жəне тиісті сілтемелер
реттеледі: ауыстырушы жазба ҥшін синонимдер тізбегіндегі алдыңғы
жазбада ауыстырылатын жазбаның жаңа орнына көрсеткіш енгізіледі,
аталған ауыстырлатын жазбадағы көрсеткіштер бҧрынғыдай қалады.
«Заңсыз» жазба аусытырылған соң енгізілетін жазба өзінің заңды
орнына орналастырылады жəне синонимдердің жаңа тізбегінде бірінші
жазба болып енгізіледі.
Жазбаларды жою тетіктері көбінесе стратегиядағы асыра толтыру
саласымен жою тетіктеріне ҧқсас жəне келесі əрекеттерге алып келеді.
Егерде жойылатын жазба синонимдер тізбегіндегі бірінші жазба
болатын болса, онда жоюдан кейін оның орнына синонимдер тізбегінің
келесі (екінші) жазбасы ауыстырылады жəне бар болған жағдайда,
синонимдер тізбегінің ҥшінші жазбасындағы көрсеткіштерге тиісті
тҥзету жҥргізіледі.
Егерде синонимдер тізбегініңортасында тҧратын жазба жойылатын
болса, онда көрсеткіштерді тҥзету ғана жҥргізіледі: алдыңғы
жазбадағы
жойылатын
жазбаның
көрсеткіші
келесі
жойылатын
жазба
көрсеткішіне ауыстырылады, жойылатыннан кейінгі жазбадағы
алдыңғы жазба көрсеткіші алдыңғы жойылатын жазба көрсеткішіне
ауыстырылады.
Индекс файлдары. Файл қҧрылымдарында хэш-адрестеудің
жоғары тиімділігіне қарамастан, ҥнемі тиісті функцияны табу мҥмкін
емес,
сондықтан
бірінші
кілт
бойынша
қолжетімділік
ҧйымдастырылған кезде, индекс файлдары кеңінен қолданылады.
Индекс файлдары екі бөліктен тҧратын файлдар ретінде ҧсынылуы
мҥмкін. Алдымен блоктардың бҥтін сандарын қабылдайтын индекстік
салаорналасқан, одан кейін файлдың барлық жазбалары кезеңмен
орналасқан негізгі сала орналасады.
Кейбір жҥйелерде индекс файлдары қайталама кілтке кіру ҥшін
пайдаланылатын инверттелген тізімдер тҥріндегі ҧйымдастырылған
файлдар деп аталады. Индекстің жəне негізгі салаларының
ҧйымдастырылуына байланысты файлдардың екі тҥрі бар: тығыз
индексі бар (индексті-тікелей файлдар) жəне тығыз емес индекспен
(индексті-кезеңді файлдар).
Тығыз индексі бар файлдар немесе индекс-тікелей файлдар. Бҧл
файлдарда негізгі сала еркін тəртіпте орналасқан, бірдей ҧзындықтағы
жазбалардың тізбегінен тҧрады, ал индексті жазба қҧрылымы келесі
тҥрлерден тҧрады:
Кілттің мағынасы
Жазбаның
нөмірі
Мҧнда
кілттің мағынасы – ол бірінші кілттің мағынасы, ал жазбаның
нөмірі – ол бірінші кілттің аталған мағынасына ие негізгі саладағы
жазбаның реттік нөмірі болып табылады.
