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

V>Эта особенность была не только Акробате, но и в другой популярной на тот момент проге по верстке печатного материала — в Word Press.
V>И все прекрасно понимали, почему так — потому что это инструмент для вёрстки, а не для работы над текстом.
Ну, то есть коненсус. Ок.

V>Если бы ты не кривлялся там, а был настроен на предметный разговор, я бы читал твои ответы.
V>Но как только опять начинаешь маяться хернёй — просто облом тратить время, бо а смысл?
V>Я там допустил только одну ошибку — в оценке размера реального дерева, на основе бинарного, которое со сжатией информации.
Размер реального дерева, хоть бинарного, хоть B-дерева, это O(N) от исходных данных.
V>Оно там оценочного размера N/K, где K порой достаточно большое, а не log N.
Ну, то есть логарифма нет.
V>Но это несущественная неточность, т.к. мы рассуждали о сжатии информации и оно, существенное сжатие, всё-равно присутствует.
Непонятно, о каком сжатии идёт речь.
На всякий случай напомню, что в обычном дереве ровно столько ссылок на сами данные, сколько записей в исходных данных.
Ваша идея про то, что можно одной ссылкой из дерева сослаться сразу на X записей исходных данных, в целом верна, хоть и лажает в деталях.
Например, кластерные индексы в MS SQL именно так и устроены — только они не зависят от наличия непрерывных диапазонов в значениях первичного ключа в исходных данных. Достаточно простой упорядоченности.
Просто "листьями" кластерного индекса являются сами страницы данных. Т.е. они тоже являются частью дерева, и никакого "сжатия" не происходит — в частности, алгоритмы split/merge при вставке и удалении записей применяются не только к branch-нодам, но и к страницам данных. И, тоже в частности, если таблица с кластерным индексом целиком влезает в одну страницу, то никаких дополнительных страниц на индекс не выделяется — сама эта страница и является корнем индекса. Если считать по вашей методике, это означает бесконечный "коэффициент сжатия" — нулевой размер "индекса" при ненулевом размере данных.
А если считать по общепринятой, то по-прежнему имеем O(N).
Страницы предыдущего уровня в ссылках на страницы данных никаких "длин диапазонов" не хранят — достаточно просто хранить PageRef на страницу данных и минимальное значение ключа на ней. Это позволяет увеличить branch factor по сравнению с вашей идеей.

Для time series, которые вам кажется удобно хранить просто в виде "отсортированного списка" напомню, что поиск по B-дереву всё ещё эффективнее бинарного поиска по отсортированному массиву, даже если его удалось поднять в память одним непрерывным блоком — из-за локальности кэша. Так что никаких отдельных "time-series" индексов не существует за ненадобностью.

Про мелкие ошибки в виде забытых значений ключей в branch-страницах B-дерева я уже и вовсе молчу — это можно списать на опечатки при наборе.

Самое главное-то в том, что PGM индекс по-прежнему уделывает B-деревья, эффективнее которых для диапазонных запросов за предыдущие 30+ лет ничего не придумали.