Вчені з Массачусетського технологічного інституту, зробили відкриття, яке може призвести до більш ефективного зберігання і вилучення даних в базах даних.
Висновки групи належать до так званих «хеш-таблиць з лінійним зондуванням», які були введені в 1954 році і є одними з найстаріших, найпростіших і найшвидших структур даних, доступних сьогодні. Структури даних надають способи організації та зберігання даних на комп'ютерах, при цьому хеш-таблиці є одним з найбільш часто використовуваних підходів. У хеш-таблиці з лінійним зондуванням позиції, в яких може зберігатися інформація, лежать уздовж лінійного масиву.
Припустимо, наприклад, що база даних призначена для зберігання номерів соціального страхування 10 000 осіб, - пропонує автор дослідження Вільям Кужмаул. «Ми беремо ваш номер соціального страхування, x, і потім обчислюємо хеш-функцію x, h (x), яка дає вам випадкове число від одиниці до 10 000». Наступний крок - взяти це випадкове число h (x), перейти в цю позицію в масиві і помістити в це місце x, номер соціального страхування.
Він пояснює, що якщо щось вже займає це місце, "ви просто переходите до наступної вільної позиції і кладете номер туди. Звідси і термін "лінійне зондування", коли ви продовжуєте лінійно рухатися вперед, поки не знайдете відкрите місце ". Щоб пізніше отримати номер соціального страхування x, ви просто переходите в позначене місце h (x), а якщо його там немає, ви рухаєтеся вперед, поки не знайдете x або не перейдете у вільне положення і не прийдете до висновку, що x дорівнює «ні» у вашій базі даних.
Існує кілька інший протокол для видалення елемента, наприклад номера соціального страхування. Якщо ви просто залишили порожнє місце в хеш-таблиці після видалення інформації, це може викликати плутанину, коли ви пізніше спробуєте знайти щось ще, так як вільне місце може помилково вказувати на те, що елемент, який ви шукаєте, ніде не може бути знайдений в базі даних. Щоб уникнути цієї проблеми, пояснює Вільям Кужмаул, «ви можете перейти до місця, де елемент був видалений, і поставити там невеликий маркер, званий» tombstone «(надгробок), який означає, що раніше тут був елемент, але тепер його немає».
Цієї загальної процедури дотримуються понад півстоліття. Але за весь цей час майже всі, хто використовував хеш-таблиці з лінійним зондуванням, припускали, що якщо ви дозволите їм заповнитися занадто сильно, довгі ділянки зайнятих місць будуть об'єднуватися, утворюючи «кластери». У результаті час, необхідний для пошуку вільного місця, різко зросте - по суті, квадратично - до такої міри, що це буде непрактично.
Але цей перевірений часом принцип, який довгий час виступав проти високих факторів навантаження, був повністю спростований роботою Вільяма Кужмаула і його колег, Майкла Бендера з Університету Стоуні-Брук і Бредлі Кужмаула з Google. Вони виявили, що для додатків, в яких кількість вставок і видалень залишається приблизно однаковою, а кількість доданих даних приблизно дорівнює кількості віддалених, хеш-таблиці з лінійним зондуванням можуть працювати з великими обсягами зберігання без шкоди для швидкості.
Крім того, дослідники розробили нову стратегію, звану «кладовищенське хешування», яка включає в себе штучне збільшення кількості надгробків, що поміщаються в масив, до тих пір, поки вони не займуть приблизно половину вільних місць. Ці надгробки потім резервують місця, які можна використовувати для майбутніх вставок.
За словами вчених, цей підхід, який суперечить тому, чого зазвичай вчать людей, «може призвести до оптимальної продуктивності в хеш-таблицях з лінійним зондуванням». Або, як він і його співавтори стверджують у своїй статті, "добре продумане використання надгробків може повністю змінити... ландшафт того, як поводиться лінійне зондування ".
Вчені виклали отримані результати в опублікованій статті, яка буде представлена в лютому на симпозіумі з основ комп'ютерних наук (FOCS) в Боулдері.
