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

V>Мы про хранение индексов.
V>А это не чисто-теоретическое B-tree.


S>>Что это за индекс, лист которого индексирует единичную запись?

V>А что ты вообще делаешь на сайте программистов? ))
Развлекаюсь.
V>Лист индекса не является листом бинарного дерева, это служебная запись о координатах целевой записи или нескольких их.
Эмм. Откуда появилось слово "бинарное"? Вы где-то видели бинарное B-дерево?

V>Т.е. узел дерева — это не единичный тип данных, а сумма типов:
V>

V>data RecordRef = SingleRecordRef (Page, Offset) | RecordRangeRef (Page, Offset, Count)
V>type KeyEntry key = (key, RecordRef)
V>data TreeNode key = Nil | BinNode (TreeNode key, TreeNode key) | LeafNode [KeyEntry key]
V>

Удивительное рядом. Я так понял, что ваш RecordRangeRef должен обработать экзотический случай неуникального кластерного индекса? Нет, это работает не так.
Непонятно, почему у вас в промежуточных узлах всего по две ссылки на детей, куда из них подевались значения ключей.

V>И зачем ты повторяешь свои глупости?
Я не повторяю, я пытаюсь нащупать смысл в ваших постах.
V>Мы говорили про RAM.
Пока что мы пытаемся выяснить, что вы называете "ростом дерева".

V>Выше схематично расписан тип листового узла индекса на Хаскель (на знакомом тебе C# описывать union-ы через иерархию наследников слишком многословно).
V>Еще выше картинка.

V>Включи воображение и представь, что на картинке в листовом узле не список единичных узлов, а одна записись на диапазон их, когда значения ключа идут без пропусков в этом диапазоне и соотв. строки данных хранятся на одной странице.
Попробуем разобрать эту мысль. Начнём с конца.
0. Попадут ли строки данных на одну страницу или нет зависит не от наличия пропусков в диапазоне ключей, а от соотношения размера записи и страницы.
1. Ну, ок, мы, наверное, можем сыграть на том, что у нас записи с ключами 58, 60, 61, 62, 63, 65 попали на одну страницу, тогда мы типа "экономим место" в индексе, сославшись сразу на четыре из них в одной KeyEntry вида (60, <Page>, 1, 4). Но какой смысл оставлять в листовом узле только эту KeyEntry? Он размером в 8кб, туда можно ещё много KeyEntries напихать. Так что по-прежнему непонятен смысл такого листа, который индексирует единичную запись. Тем более, что записей-то тут на самом деле ажно 4.
Ну, и, повторюсь, именно так никто не делает, т.к. это неэффективно.

V>Диапазон.
Это всё про ту же картинку?

V>Вопрос в силе.
А сила — в правде.

S>>Обычно в рассуждениях про древовидные структуры оперируют двумя параметрами: размер и глубина. Вы, как обычно, вводите какую-то новую терминологию, неведомую простым смертным.

V>И расти может общее кол-во узлов дерева, ес-но.
V>Какие там еще могли быть варианты, что ты так упорно уточнял?
Ну, ок. Вот только количество узлов дерева растёт как O(1) от количества индексируемых записей. Потому я и уточнял, что бред выходит.

V>Какой именно вопрос?
Что такое n-tree и благодаря чему оно эффективнее чем B-tree.
V>И почему ты задаёшь подобные бестолковые вопросы?
Потому что то, что вы пишете, выглядит как бред. И либо я чего-то фундаментально не понимаю, либо вы. Я очень надеюсь на первое — потому и выясняю такие простые вещи.

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

V>Отличается представлением даных.
V>Разумеется, на бинарном дереве эта задача решаема.
Откуда опять этот термин "бинарное дерево"???? В СУБД никаких бинарных деревьев не используют с 1970х.

V>Но есть более простые сценарии:
V>- значения добавляются только с монотонно увеличивающимся ключом;
V>- старые записи никогда не удаляются.

V>В итоге, дерево не нужно, заменяется в представлении на сортированный плоский список (или набор таких списков), т.е. вместо дорогой итерации в памяти по графу дерева происходит двоичный поиск по плоскому списку (или по золотому сечению, что для бухгалтерии чаще эффективней). Представление такого индекса в памяти примерно вчетверо экономнее классического b-tree индекса и работает оно в несколько раз шустрее.
Ну, во-первых, непонятно, с чего это вдруг "итерация по графу дерева" будет шибко дороже двоичного поиска.
Во-вторых, непонятно, влезет ли весь нужный нам список в RAM или нет — точнее, почему мы должны полагаться на его влезаемость. Если мы говорим о данных на диске, то у бинарного поиска всё будет плохо с нагрузкой на IO.
В-третьих, может по сравнению с бинарным деревом представление и будет вчетверо более эфффективным, а вот по сравнению с B-деревьями — нет. Там будут копейки разницы, которые многократно окупаются дружелюбием к кэшу.

V>А зачем тебе оговорка про скалярный тип данных?
V>В чём подвох?
В том, что словосочетание "вероятностные индексы" я встречал только в применении ко всяким задачам кластеризации документов и "поискам по релевантности".
V>Чем не устраивает пара (integer, integer)?
Вполне устраивает. Расскажите на примере пары (integer, integer).

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

S>>Ну, вот PGM-индекс придумали.

V>Нет, не придумали.
V>Никакого нового принципа индексирования не показали.

V>Вот я тебе показал сжатие информации через хранение диапазонов ключей в единичной записи листового узла (а записей в листовом узле может быть несколько).
Ну, это вы как раз пытаетесь изобрести PGM индекс с ограничением на коэффициент линейности равный единице. Но ваш дизайн всё ещё менее эффективен, чем классический кластерный индекс в MS SQL на основе B+-дерева.

V>Но это не тянет на "придумал", это и так давно известно, с самого что ни на есть начала этой предметной области.

V>По одному и тому же предмету то демонстрируешь глубокое владение мало кому интересными тонкостями, то плаваешь в самых базовых вещах, вызываешь недоумение.
Ну, никогда же ведь не поздно научиться чему-то новому.

V>Однако же, ускорили почти вдвое (если это не устаревшая уже информация, т.к. тщательно не слежу).
"Вдвое" — это какие-то несущественные вещи. Интересна асимптотика, и ускорения в разы.
Ну, вот как ребята в MemSQL — которые устали уговаривать начальство в Редмонде запилить columnStore или хотя бы bitmap indices, и в итоге получили реализацию, которая при выполнении select count(*) по предикату окучивает больше 200 записей за такт.

V>Например, в time series такая же оценка сложности кол-ва операций как у бинарного дерева, но работает в несколько раз быстрее.
V>В зависимости от как повезет до 10-20 раз быстрее.
Повторюсь: зачем вы сравниваете с бинарными деревьями, которые никто в здравом уме не применяет? B-деревья работают быстрее даже чисто-в-памяти, а при работе с диском так и вообще говорить не о чем.

V>Вдогонку, забыл самое главное про time series.
Да, я тоже внимание обратил.
V>Cамую мощь time series показывают не при отдельном поиске значения, а при join.
V>В этом случае реальная стоимость поиска значения приближается к O(1) вместо O(log(N)), т.к. курсор или остаётся на текущей строке курсов валют, или передвигается на одну запись к предыдущей дате, т.е. итерироваться надо от новых дат к старым.
Впрочем, ровно как и B+-дерево. Так что пока непонятно, что же такое time series индекс, и чем именно он отличается.