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

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

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


S>Или о чём?

Да о твоём странном невежестве и логических ошибках.
Сорри, не дописал пред. сообщение (отвлекли), можно вернуться, прочитать дописанный вариант.


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

А что ты вообще делаешь на сайте программистов? ))


Лист индекса не является листом бинарного дерева, это служебная запись о координатах целевой записи или нескольких их.
Т.е. узел дерева — это не единичный тип данных, а сумма типов:

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

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

И зачем ты повторяешь свои глупости?
Мы говорили про RAM.


S>Было бы интересно увидеть индекс с логарифмической (или хотя бы сублинейной) асимптотикой этого параметра.

Кошмар... ))

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

Включи воображение и представь, что на картинке в листовом узле не список единичных узлов, а одна записись на диапазон их, когда значения ключа идут без пропусков в этом диапазоне и соотв. строки данных хранятся на одной странице.


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

Диапазон.


V>>Действительно, что такое рост? ))
S>Ну, так всё же?

Вопрос в силе.


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

Я гарантирую, что никакой новой терминологии.
Просто ты несешь какую-то околесицу, на которую я уже не знаю, как реагировать...

У меня и так же перебор язвительности (твои манеры заразны, старайся их контроллировать).
Ну какие в опу два параметра "размер и глубина" для сбалансированного бинарного дерева, Синклер, у тебя аккаунт украли?
Длина от корня до любого листа не может отличаться более чем на 1, т.е. одно через другое представимо, если речь об оценке размера дерева, т.е. об общем кол-ве узлов.

И расти может общее кол-во узлов дерева, ес-но.
Какие там еще могли быть варианты, что ты так упорно уточнял?


V>>Мы это уже обсуждали.
S>Не припомню такого. И вопрос про n-tree тоже пока что в силе.

Какой именно вопрос?

И почему ты задаёшь подобные бестолковые вопросы?
Нельзя ли уже по делу или не отнимать у коллег время?


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

Отличается представлением даных.
Разумеется, на бинарном дереве эта задача решаема.
Просто само бинарное дерево не нужно.

Бинарное дерево — это ответ на задачи про удалить/добавить в произвольное место/сбалансировать.
На самом-то деле требуется обычный бинарный поиск, где бинарное сбалансированное дерево лишь занимается подготовкой данных к такому поиску.

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

В итоге, дерево не нужно, заменяется в представлении на сортированный плоский список (или набор таких списков), т.е. вместо дорогой итерации в памяти по графу дерева происходит двоичный поиск по плоскому списку (или по золотому сечению, что для бухгалтерии чаще эффективней). Представление такого индекса в памяти примерно вчетверо экономнее классического b-tree индекса и работает оно в несколько раз шустрее.

И мы это уже обсуждали когда-то.
Как минимум я тебе упоминал про time series и ты соглашался, т.е. старательно делал вид, что понимаешь, о чём речь. ))

Разумеется, эта техника подходит не только для time series, оные просто сочная отсылка к примеру подобного сценария.


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

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

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


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

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

Вот я тебе показал сжатие информации через хранение диапазонов ключей в единичной записи листового узла (а записей в листовом узле может быть несколько).
Но это не тянет на "придумал", это и так давно известно, с самого что ни на есть начала этой предметной области.

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


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

Однако же, ускорили почти вдвое (если это не устаревшая уже информация, т.к. тщательно не слежу).
И там никакой "придумки".
Обычное вылизывание сугубо инженерного плана способно изменять характеристики в некое кол-во раз.
Но неспособно изменять в плане оценки сложности O, а интересует именно это.

Например, в time series такая же оценка сложности кол-ва операций как у бинарного дерева, но работает в несколько раз быстрее.
В зависимости от как повезет до 10-20 раз быстрее.

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

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

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


S>Или о чём?

Да о твоём странном невежестве и логических ошибках.
Сорри, не дописал пред. сообщение (отвлекли), можно вернуться, прочитать дописанный вариант.


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

А что ты вообще делаешь на сайте программистов? ))


Лист индекса не является листом бинарного дерева, это служебная запись о координатах целевой записи или нескольких их.
Т.е. узел дерева — это не единичный тип данных, а сумма типов:

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

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

И зачем ты повторяешь свои глупости?
Мы говорили про RAM.


S>Было бы интересно увидеть индекс с логарифмической (или хотя бы сублинейной) асимптотикой этого параметра.

Кошмар... ))

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

Включи воображение и представь, что на картинке в листовом узле не список единичных узлов, а одна записись на диапазон их, когда значения ключа идут без пропусков в этом диапазоне и соотв. строки данных хранятся на одной странице.


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

Диапазон.


V>>Действительно, что такое рост? ))
S>Ну, так всё же?

Вопрос в силе.


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

Я гарантирую, что никакой новой терминологии.
Просто ты несешь какую-то околесицу, на которую я уже не знаю, как реагировать...

У меня и так же перебор язвительности (твои манеры заразны, старайся их контроллировать).
Ну какие в опу два параметра "размер и глубина" для сбалансированного бинарного дерева, Синклер, у тебя аккаунт украли?
Длина от корня до любого листа не может отличаться более чем на 1, т.е. одно через другое представимо, если речь об оценке размера дерева, т.е. об общем кол-ве узлов.

И расти может общее кол-во узлов дерева, ес-но.
Какие там еще могли быть варианты, что ты так упорно уточнял?


V>>Мы это уже обсуждали.
S>Не припомню такого. И вопрос про n-tree тоже пока что в силе.

Какой именно вопрос?

И почему ты задаёшь подобные бестолковые вопросы?
Нельзя ли уже по делу или не отнимать у коллег время?


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

Отличается представлением даных.
Разумеется, на бинарном дереве эта задача решаема.
Просто само бинарное дерево не нужно.

Бинарное дерево — это ответ на задачи про удалить/добавить в произвольное место/сбалансировать.
На самом-то деле требуется обычный бинарный поиск, где бинарное сбалансированное дерево лишь занимается подготовкой данных к такому поиску.

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

В итоге, дерево не нужно, заменяется в представлении на сортированный плоский список (или набор таких списков), т.е. вместо дорогой итерации в памяти по графу дерева происходит двоичный поиск по плоскому списку (или по золотому сечению, что для бухгалтерии чаще эффективней). Представление такого индекса в памяти примерно вчетверо экономнее классического b-tree индекса и работает оно в несколько раз шустрее.

И мы это уже обсуждали когда-то.
Как минимум я тебе упоминал про time series и ты соглашался, т.е. старательно делал вид, что понимаешь, о чём речь. ))

Разумеется, эта техника подходит не только для time series, оные просто сочная отсылка к примеру подобного сценария.


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

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

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


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

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

Вот я тебе показал сжатие информации через хранение диапазонов ключей в единичной записи листового узла (а записей в листовом узле может быть несколько).
Но это не тянет на "придумал", это и так давно известно, с самого что ни на есть начала этой предметной области.

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


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

Однако же, ускорили почти вдвое (если это не устаревшая уже информация, т.к. тщательно не слежу).
И там никакой "придумки".
Обычное вылизывание сугубо инженерного плана способно изменять характеристики в некое кол-во раз.
Но неспособно изменять в плане оценки сложности O, а интересует именно это.

Например, в time series такая же оценка сложности кол-ва операций как у бинарного дерева, но работает в несколько раз быстрее.
В зависимости от как повезет до 10-20 раз быстрее.

Вдогонку, забыл самое главное про time series.

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