Стендап Сьогодні 📢 Канал в Telegram @stendap_sogodni

🤖🚫 AI-free content. This post is 100% written by a human, as is everything on my blog. Enjoy!

01.09.2023

Як OpenSearch індексує числа

Вчора я написав трохи застарілу інформацію: насправді десь з 2016 року Lucene вже не зберігає числа у вигляді рядків. Тобто, така можливість залишилась, але тепер є інший спосіб індексування: k-d дерево. Я не пишу “кращий”, бо все залежить від того, що з ним робити.

K-d дерево це дерево множин точок у K-вимірному просторі. Кожен рівень дерева ділить множину навпіл за одним з вимірів. Таким чином, дерево є збалансованим, тобто має рівну кількість точок в кожній гілці — а значить, мінімальну кількість розгалужень.

Але ми хотіли індексувати числа. До чого тут якісь простори? Так, технічно число задає точку в 1-вимірному просторі, а узагальнення на багато вимірів дозволяє використати ту саму структуру даних також для географічних координат, діапазонів та інших застосувань, де важливо порівнювати одночасно декілька показників. У випадку чисел, дерево просто ділить діапазон навпіл, поки не досягне зазначеного розміру множини, що залишається.

В Lucene K-d дерева зберігаються окремо від інвертованого індексу (словника, про який я писав вчора.) Тобто заради ефективності пошуку архітектори впровадили цілу нову структуру даних та формат файлу. З цього боку зрозуміло, чому обрали саме k-d дерева, які покривають багато потреб, а не тільки пошук чисел.

Пошук в K-d дереві відбувається завжди за діапазоном. Кожний вузол дерева визначає діапазон значень всередині. Він може бути або цілком всередині, або цілком ззовні, або перетинати діапазон пошуку. Ті вузли, що всередині, додаються до результату, ззовні — відкидаються, та тільки в ті, що перетинають, доведеться спускатись на наступний рівень та дивитись на менші підмножини. Таким чином ми маємо справу з найбільшими можливими множинами, та відповідно — з найменшою їх кількістю.

Тепер, про доцільність такого індексу в контексті чисел. Якщо вам потрібно шукати числа за діапазоном, то він ефективний, питань нема. А якщо числа — це ідентифікатори, а шукати потрібно тільки по рівності, то алгоритм залишиться такий самий — хоч для діапазону з одного значення. Ба більше, оскільки множини в k-d дереві не доходять до такої деталізації, то наприкінці пошуку відбувається перебір — не дуже великий, але все ж зайвий.

Тому для індексації чисельних ідентифікаторів краще брати тип keyword. Тоді для них буде використаний звичайний інвертований індекс, оптимізований саме для пошуку конкретного значення.