Ефективнiсть методу двiйкового пошуку записiв у файлах баз даних у випадку розподiлу ймовiрностей звертання до записiв за законом Зiпфа

Анотація

Основний акцент пiд час розв’язування рiзноманiтних задач з використанням концепцiї баз даних переноситься з процедур опрацювання iнформацiї на процедури органiзацiї збереження та пошуку iнформацiї в базах даних. Тому продуктивнiсть обчислювальних систем, орiєнтованих на опрацювання iнформацiї у великих базах даних, головним чином визначається ефективнiстю методiв пошуку iнформацiї у файлах баз даних. Оскiльки в бiльшостi систем опрацювання iнформацiї типовими є випадки нерiвномiрного розподiлу ймовiрностей звертання до записiв файлiв, то дослiдження ефективностi методiв пошуку проводиться для таких типових законiв нерiвномiрного розподiлу ймовiрностей як бiнарний, закон Зiпфа, узагальнений закон. За критерiй ефективностi методiв приймається математичне сподiвання кiлькостi порiвнянь, необхiдних для пошуку запису у файлi. Деякi частковi результати дослiдження ефективностi методiв пошуку одержанi зарубiжними авторами, зокрема вони вiдображенi у монографiях Д. Кнута i Дж. Мартiна. Бiльш повнi дослiдження проведенi в працях Цегелика Г.Г. Для пошуку запису у файлi можна використати рiзнi методи: послiдовний перегляд; однорiвневий чи багаторiвневий блоковий пошук; двiйковий пошук; метод пошуку, що враховує розподiл ймовiрностей звертання до записiв; методи пошуку, що використовують iндекси тощо. Ефективнiсть цих методiв для рiзних законiв розподiлу ймовiрностей звертання до записiв є рiзною. Вважатимемо, що файл бази даних упорядкований за зростанням значень ключа. У статтi виведено формулу для обчислення математичного сподiвання кiлькостi порiвнянь, необхiдних для пошуку запису у файлi, у випадку розподiлу ймовiрностей звертання до записiв за законом Зiпфа. Зроблено порiвняння ефективностi методу послiдовного перегляду та методу двiйкового пошуку у цьому випадку, а також порiвняння ефективностi двiйкового пошуку у випадку рiвномiрного розподiлу ймовiрностей i розподiлу за законом Зiпфа. На графiках показана залежнiсть математичного сподiвання кiлькостi порiвнянь вiд кiлькостi записiв у файлi у випадку розподiлу ймовiрностей звертання до записiв за законом Зiпфа.