Здравствуйте, <Аноним>, Вы писали:

А>Что есть сие, какова структура, каковы алгоритмы?
А>Просьба не путать с многомерным массивом.
А>Просьба разъяснить, если кто знает.
Ууу... В настоящее время неизвестны коммерческие реализации многомерных индексов, которые бы гарантировали логарифмическое быстродействие всех операций одновременно с филл-фактором (как, например, B-tree для линейных индексов). В Cache, например, применяются R-tree. Они не гарантируют филлфактор, и при частых удалениях вырождаются. Поэтому гуры рекомендуют реиндексинг — вынимание элементов из индекса и новая вставка. Это балансирует дерево, уменьшая время поиска. Я встречал статью с описанием алгоритма, который вроде как гарантирует логарифмичность всех операций при филлфакторе >= 30%. Увы, реализации этой идеи я не встречал.

Что есть сие, какова структура, каковы алгоритмы?
Просьба не путать с многомерным массивом.
Просьба разъяснить, если кто знает.

Евгений Каратаев.

Здравствуйте, Sinclair, Вы писали:

А>>Что есть сие, какова структура, каковы алгоритмы?
А>>Просьба не путать с многомерным массивом.
А>>Просьба разъяснить, если кто знает.
S>Ууу... В настоящее время неизвестны коммерческие реализации многомерных индексов, которые бы гарантировали логарифмическое быстродействие всех операций одновременно с филл-фактором (как, например, B-tree для линейных индексов). В Cache, например, применяются R-tree. Они не гарантируют филлфактор, и при частых удалениях вырождаются. Поэтому гуры рекомендуют реиндексинг — вынимание элементов из индекса и новая вставка. Это балансирует дерево, уменьшая время поиска. Я встречал статью с описанием алгоритма, который вроде как гарантирует логарифмичность всех операций при филлфакторе >= 30%. Увы, реализации этой идеи я не встречал.

Понял.
А ссылочку на источник, что в cache применяется R-tree?

Евгений Каратаев

Здравствуйте, <Аноним>, Вы писали:
А>Понял.
А>А ссылочку на источник, что в cache применяется R-tree?
Потерял Вроде в какой-то статье проскакивало... Но теперь что-то не могуглится..

Здравствуйте, Sinclair, Вы писали:

А>>А ссылочку на источник, что в cache применяется R-tree?
S>Потерял Вроде в какой-то статье проскакивало... Но теперь что-то не могуглится..

Понял.
На самом деле там B*

Евгений Каратаев.

Здравствуйте, <Аноним>, Вы писали:

А>Понял.
А>На самом деле там B*

Занятно. То есть многомерных индексов у них нет?

Здравствуйте, Sinclair, Вы писали:

S>Занятно. То есть многомерных индексов у них нет?

Нет. Есть многомерные массивы, но реализованы на B* деревьях.
Типа FFF("aaa","bbb")="ccc"

Евгений Каратаев.

Здравствуйте, Sinclair, Вы писали:

S>Ууу... В настоящее время неизвестны коммерческие реализации многомерных индексов, которые бы гарантировали логарифмическое быстродействие всех операций одновременно с филл-фактором (как, например, B-tree для линейных индексов). В Cache, например, применяются R-tree. Они не гарантируют филлфактор, и при частых удалениях вырождаются. Поэтому гуры рекомендуют реиндексинг — вынимание элементов из индекса и новая вставка. Это балансирует дерево, уменьшая время поиска. Я встречал статью с описанием алгоритма, который вроде как гарантирует логарифмичность всех операций при филлфакторе >= 30%. Увы, реализации этой идеи я не встречал.

А не про это шла речь?
http://mistral.in.tum.de

Евгений Каратаев.

Здравствуйте, <Аноним>, Вы писали:
А>А не про это шла речь?
А>http://mistral.in.tum.de
Неа. Там как-то по-другому пространство делили. Попробую найти у себя эту статью.

Здравствуйте, <Аноним>, Вы писали:
А>Нет. Есть многомерные массивы, но реализованы на B* деревьях.
А>Типа FFF("aaa","bbb")="ccc"
Я вот это не очень понимаю. Оно же тогда должно страшно тормозить, когда я запрашиваю FFF("aaa") или FFF("bbb")?
А>Евгений Каратаев.

Здравствуйте, Sinclair, Вы писали:

А>>Нет. Есть многомерные массивы, но реализованы на B* деревьях.
А>>Типа FFF("aaa","bbb")="ccc"
S>Я вот это не очень понимаю. Оно же тогда должно страшно тормозить, когда я запрашиваю FFF("aaa") или FFF("bbb")?

Наоборот. Это условная сокращенная запись дерева. Примерно как если есть дерево
с именем FFF, в нем есть узел с ключом "aaa" (строковый ключ, или индекс), и этот узел тоже есть дерево, в нем узел с ключом "bbb", и в этот узел записана строка "ccc". Здесь "aaa" — индекс первого уровня. FFF("bbb") — это тоже узел первого уровня, "bbb" — его индекс.
FFF("aaa","bbb") — узел второго уровня.
"Страшно тормозить" — это слухи.

Евгений Каратаев.

Здравствуйте, <Аноним>, Вы писали:

А>Наоборот. Это условная сокращенная запись дерева. Примерно как если есть дерево
А>с именем FFF, в нем есть узел с ключом "aaa" (строковый ключ, или индекс), и этот узел тоже есть дерево, в нем узел с ключом "bbb", и в этот узел записана строка "ccc". Здесь "aaa" — индекс первого уровня. FFF("bbb") — это тоже узел первого уровня, "bbb" — его индекс.
А>FFF("aaa","bbb") — узел второго уровня.
А>"Страшно тормозить" — это слухи.
Странно. Поясняю: что мне делать, если я ищу все такие узлы в FFF(), у которых второй ключ равен "bbb"? Для B-tree это означает линейный просмотр. Т.е. "страшно тормозить".

Здравствуйте, Sinclair, Вы писали:

А>>Наоборот. Это условная сокращенная запись дерева. Примерно как если есть дерево
А>>с именем FFF, в нем есть узел с ключом "aaa" (строковый ключ, или индекс), и этот узел тоже есть дерево, в нем узел с ключом "bbb", и в этот узел записана строка "ccc". Здесь "aaa" — индекс первого уровня. FFF("bbb") — это тоже узел первого уровня, "bbb" — его индекс.
А>>FFF("aaa","bbb") — узел второго уровня.
А>>"Страшно тормозить" — это слухи.
S>Странно. Поясняю: что мне делать, если я ищу все такие узлы в FFF(), у которых второй ключ равен "bbb"? Для B-tree это означает линейный просмотр. Т.е. "страшно тормозить".

Если я правильно понял вопрос, то ответ такой:
строить индексную структуру для такого поиска, например при записывании узла
FFF("aaa","bbb")="ccc"
писать что мы потом хотим найти, например
iFFF("bbb","aaa")="" или еще что.
по узлу iFFF("bbb") проходим по всем его дочерним, получаем например "aaa".
Если интересно про индексы в cache, то велкам ту http://karataev.nm.ru/ind
Собрал в кучку некоторые моменты.

Евгений Каратаев.