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

V>Есть неоднородность представления дерева на листьях в зависимости от вида индекса и способа представления.
V>Иногда лист индекса может содержать ренж, т.е. индексировать сразу набор записей, иногда явный список записей, иногда единичную запись.
Мы всё ещё про B-tree? Или о чём? Что это за индекс, лист которого индексирует единичную запись?

V>То бишь, оценка размера деревянного индекса может быть как log(N), так и log(N) + N.
Повторюсь: что такое "размер" деревянного индекса? Общее место под хранение всего этого индекса?
Было бы интересно увидеть индекс с логарифмической (или хотя бы сублинейной) асимптотикой этого параметра.

V>Для большинства первичных ключей, которые имеют целочисленную природу и по которым записи сортированы, деревянный индекс имеет минимальное представление, бо хранит только ренжи в лстьях.
Что такое "ренж"?

V>Действительно, что такое рост? ))
Ну, так всё же? Обычно в рассуждениях про древовидные структуры оперируют двумя параметрами: размер и глубина. Вы, как обычно, вводите какую-то новую терминологию, неведомую простым смертным.

S>>Кстати, вопрос про n-tree из соседнего треда всё ещё в силе. Вместе с вопросом про индексы time series

V>Мы это уже обсуждали.
Не припомню такого. И вопрос про n-tree тоже пока что в силе.
V>Есть валюты, есть даты изменений валют, тебе надо делать join по датам от таблицы операций на таблицу курсов валют, а в той содержатся, допустим, только даты изменений курса, но не курс на каждый день.
И как же устроен индекс, который позволяет эффективно выполнять эту операцию? Или нет, давайте так: что мешает СУБД выполнять такую операцию эффективно при использовании B-tree индекса?
Или даже так: чем отличается специализированный time series индекс для этой задачи от банального B-tree?

S>>и вероятностные индексы.

V>Мы это тоже уже обсуждали — которые имеет смысл перестраивать от статистики, инфы более чем полно.
Дайте же ссылку на примеры этой инфы, которой "полно". "Перестраивать от статистики" — это интересная идея, но таких индексов я в промышленном применении не знаю. По крайней мере для скалярных данных.

V>Ничего нового в этой области давным давно нет.
Нового для меня.
V>По крайней мере в теории.
Ну, вот PGM-индекс придумали.

V>"Новостью" в плане реляционных СУБД последний примерно десяток лет является то, что реляционные СУБД повернулись лицом к хранению слабоструктурированных данных, т.е. в них вылизали достаточно примитивный сценарий работы с отдельными таблицами, у каждой из которых единственный индекс-ключ, но размер таблиц большой.
Это как раз ничего нового. Те же пестни на новый лад.