|
UB-дерево UB-дерево — збалансоване дерево для ефективного пошуку та вилучення з багатовимірних даних. СтруктураUB-дерево є B⁺-деревом, де записи зберігаються в Z-порядку[en]. Порядок обчислюється шляхом побітового чергування ключів. Вставка, видалення та точковий запит виконуються так само, як і в звичайних B⁺-деревах. Пошук по діапазону в багатовимірних точкових даних потребує алгоритму для обчислення наступного Z-значення, яке лежить в діапазоні багатовимірного пошуку, з точки, знайденої в базових даних. ІсторіяUB-дерево було запропоновано Рудольфом Баєром та Фолкером Марклем. Оригінальний алгоритм пошуку виявився з експоненційною складністю залежно від розмірності масиву, тому не здобув практичного визнання. Примітки |
