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

IT>А каков глубокий смысл?
Совсем глубокого смысла не знаю, надо в Кнута заглинуть или хотя бы в Ульмана...
Но помнится смысл в том, что это дает возможность связать все эелементы на листьевом уровне друг с другом в список (собственно по этому они и B+, + как раз означает что все элементы на листьях образуют направленый список), что позволяет:
1. Эффективно работать с групповыми выборками и различными Range Scan-ами, типа "верни мне все записи с 5-ой по 25-ю". Не надо проходить дерево сверху вниз за каждой записью, достаточно найти 5-ю и просканировать подряд, по ссылочкам все записи до 25-й.
2. Реализовать эффективный механизм предикатных блокировок.

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

M>Совсем глубокого смысла не знаю, надо в Кнута заглинуть или хотя бы в Ульмана...
+1


M>Но помнится смысл в том, что это дает возможность связать все эелементы на листьевом уровне друг с другом в список (собственно по этому они и B+, + как раз означает что все элементы на листьях образуют направленый список), что позволяет:
M>1. Эффективно работать с групповыми выборками и различными Range Scan-ами, типа "верни мне все записи с 5-ой по 25-ю". Не надо проходить дерево сверху вниз за каждой записью, достаточно найти 5-ю и просканировать подряд, по ссылочкам все записи до 25-й.

+1
Здесь еще нужно добавить, что в B+ деревьях листовые страницы могут провязываться в двухсвязный список (т.е. у каждой листовой страницы есть ссылки на левую и правую соседние листовые страницы). Это позволяет при выборке по условию (a < x < b) перебирать все x на нескольких листовых страницах не поднимаясь вверх.

Так же, отсутствие значений в родительских страницах позволяет увеличить число ключей в них. Что в результате ведет к сокращению числа родительских страниц. А это будет эффективно сказываться на кэшировании родительских страниц при работе с деревом.

И еще родительские страницы можно хранить отдельно от листовых страниц. Т.е., теоритически, родительские страницы могут располагаться в одном хранилище (индексныз файлах), а листовые страницы в друго (в файлах с данными).

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


E>И еще родительские страницы можно хранить отдельно от листовых страниц. Т.е., теоритически, родительские страницы могут располагаться в одном хранилище (индексныз файлах), а листовые страницы в друго (в файлах с данными).
А ещё размер родительских страниц может быть больше например раза в 4 для эффективности поиска, т.к. вставки в них меньше, а поиск в большем массиве более эфективен, то высоту дерева можно уменьшить, со всеми вытекающими

Здравствуйте, eao197, Вы писали:
E>Кстати, ты можешь показать в описании Reiser4, где говорится, что Reiser4 поддерживает атомарность для нескольких изменений нескольких файлов сразу (т.е. чтобы изменение нескольких файлов составляло одну транзакцию)?
У них написано, что все их операции атомарны, и есть механизмы для введения своих атомов. Т.е. там не так просто, но все же возможно получить нормальную атомарность групп операций.

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

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

Как я понимаю, обеспечивается атомарность таких операций, как creat, write и unlink. Только вот если в моей программе идет серия таких операций, по какому принципу ReiserFS поймет, что все они относятся к одной транзакции? А если реально они относятся к двум последовательно идущим транзакциям?
Я бы понял, если бы были предоставлены соответствующие системные вызовы (open_trx и close_trx) и соответственно модифицированы вызовы creat, write, unlink (чтобы можно было идентификатор транзакции указать). Но тогда не будет переносимости программы на другие FS.

eao197 wrote:
> Как я понимаю, обеспечивается атомарность таких операций, как creat,
> write и unlink. Только вот если в моей программе идет серия таких
> операций, по какому принципу ReiserFS поймет, что все они относятся к
> одной транзакции? А если реально они относятся к двум последовательно
> идущим транзакциям?
В Reiser есть понятие пространств имен — файлы могут находятся в одном
или нескольких неймспейсах.

Стандартный неймспейс — обычная FS. Может быть неймспейс для ID3-тэгов в
MP3-файлах или метаинформации об изображениях и т.п.

Для транзакции можно создать свой временный неймспейс и запихать туда
файлы. Причем если мы делаем копию, то получаем аналог snapshot'ов в БД.

Когда транзакция завершается — мы просто объединяем временный неймспейс
с целевым. Это можно сделать атомарно, причем можно даже политики
разрешения конфликтов прикрутить через механизм плугинов Reiser4.

Более того, неймспейсы могут еще и индексироваться для ускорения поиска.

Вообще, такой подход мне нравится — с одной стороны получаем много
полезных возможностей баз данных, с другой стороны, оставляем обычный
интерфейс FS.

Здравствуйте, eao197, Вы писали:
E>Как я понимаю, обеспечивается атомарность таких операций, как creat, write и unlink. Только вот если в моей программе идет серия таких операций, по какому принципу ReiserFS поймет, что все они относятся к одной транзакции?
Как я понимаю, для этого есть специальный API.
E>А если реально они относятся к двум последовательно идущим транзакциям?
E>Я бы понял, если бы были предоставлены соответствующие системные вызовы (open_trx и close_trx) и соответственно модифицированы вызовы creat, write, unlink (чтобы можно было идентификатор транзакции указать). Но тогда не будет переносимости программы на другие FS.
А ее и так не будет. Или ты ожидал, что как только ты напишешь нормальную программу с поддержкой ACID на ReiserFS4, то она автоматически за-ACIDит и на всех остальных системах?

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

S>А ее и так не будет. Или ты ожидал, что как только ты напишешь нормальную программу с поддержкой ACID на ReiserFS4, то она автоматически за-ACIDит и на всех остальных системах?

Я ожидал, что я напишу нормальную программу, которая будет поддерживать ACID на любой FS, если только FS поддерживает атомарность операции write (а это не только ReiserFS, насколько я знаю). А затачивать программу специально под особенности ReiserFS4 можно только, если эта программа под заказ разрабатывается, и заказчика такие условия устраивают.

eao197 wrote:
> Я ожидал, что я напишу нормальную программу, которая будет поддерживать
> ACID на любой FS, если только FS поддерживает атомарность операции write
> (а это не только ReiserFS, насколько я знаю).
Еще нужны блокировки и т.п. Это возможно, именно так и работают обычные
БД, вообще-то.

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

E>Я ожидал, что я напишу нормальную программу, которая будет поддерживать ACID на любой FS, если только FS поддерживает атомарность операции write.
Увы. Увы и ах. Мягко говоря, устанешь ты писать такую программу. И совершенно неясно, получишь ли ты при этом производительность лучше, чем у РДБМС.

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

S>Увы. Увы и ах. Мягко говоря, устанешь ты писать такую программу.

Да ничего, как нибудь осилю.

Sinclair wrote:
> Увы. Увы и ах. Мягко говоря, устанешь ты писать такую программу. И
> совершенно неясно, получишь ли ты при этом производительность лучше, чем
> у РДБМС.
Скорее тут будет другой вопрос: а чем это будет отличаться от Yet
Another DB?

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

C>Скорее тут будет другой вопрос: а чем это будет отличаться от Yet
C>Another DB?

Некоторая ирония чувствуется. Хочется спросить, а чем плоха YetAnotherDB, если она будет хорошо решать свою задачу?

eao197 wrote:
> C>Скорее тут будет другой вопрос: а чем это будет отличаться от Yet
> C>Another DB?
> Некоторая ирония чувствуется. Хочется спросить, а чем плоха
> YetAnotherDB, если она будет хорошо решать свою задачу?
Главный вопрос: а зачем?

Я встречал ровно одну задачу, в которой своя база данных была
эффективнее какой-нибудь SQLite/BDB. Этой задачей было создание
иерархического хранилища внутри файла

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

C>Главный вопрос: а зачем?

А шоб было

C>Я встречал ровно одну задачу, в которой своя база данных была
C>эффективнее какой-нибудь SQLite/BDB. Этой задачей было создание
C>иерархического хранилища внутри файла

Хороший пример, кстати.
Еще векторные изображения удобно в объектных базах хранить, к примеру.

Да и у BDB есть большой недостаток -- значения в ней -- это непрозрачные блоки фиксированной длины. Да еще и сама база платформо-зависимая.

Здравствуйте, eao197, Вы писали:
E>Да ничего, как нибудь осилю.
А как насчет второго утверждения?

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

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

IT>>А каков глубокий смысл?
M>Совсем глубокого смысла не знаю, надо в Кнута заглинуть или хотя бы в Ульмана...
M>Но помнится смысл в том, что это дает возможность связать все эелементы на листьевом уровне друг с другом в список (собственно по этому они и B+, + как раз означает что все элементы на листьях образуют направленый список), что позволяет:

Вернее Двухнаправленный Список (В пику Sinclair про однонаправленные итераторы)
M>1. Эффективно работать с групповыми выборками и различными Range Scan-ами, типа "верни мне все записи с 5-ой по 25-ю". Не надо проходить дерево сверху вниз за каждой записью, достаточно найти 5-ю и просканировать подряд, по ссылочкам все записи до 25-й.

Не за каждой записью, а при переходах между страницами. Но при этом ненужно хранить состояние, если оно меняется то при переходах нужно его востанавливать. Хотя версионность и здесь поможет
M>2. Реализовать эффективный механизм предикатных блокировок.

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


M>БД — это компромис, между совсем абстрактными данными, не поддающимися никакому формализму, и совершенно конкретными данными, которыми можно оперировать только зная предметную область к которой относятся эти данные.
M>Иными словами, БД говорит, что если ваши данные удовлетворяют таким-то требованиям (e.g. реляционны), то у этих данных для нас реализована: атомарность, согласованность, изолированность, сохраняемость, эффективный доступ по предикату, ect... И для того чтобы грамотно реализовать для конкретного приложания в рамках ФС, все что предоставляет БД надо угрохать кучу сил с вполне предсказуемым эффектом. Так что когда стоит вопрос выбора между ФС и БД, то это, на самом деле, вопрос — нужно ли для данного приложения всё то богатство возможностей, что предоставляет БД, или нет. И если нужно, то ответ очевиден.

Если рассматривать содержимое файла как набор множества строк данных — то да. А если рассматривать содержимое файла как единую "строку данных", где имя файла является ключем, то ФС замечательно предоставляет все то богатство возможностей, о которых ты упомянул. Например, если мы храним документы, то ФС очень даже себя оправдывает, ибо используется в последнем качестве. Если надо прикрутить развитый документооборот, то БД может хранить всякие доп. признаки и связь документов с другими объектами БД, а сам файл может спокойно себе лежать в ФС. Причем, ФС можно настроить так, чтобы избежать несанкционированного доступа вне рассматриваемой системы путем раздачи всяких прав. Более того, потери базы, как видно из форумов, случаются пока гораздо чаще, чем потери файлов. Более того, файлы зачастую можно хоть как-то восстановить, а БД — только из резервной копии. А в случае документооборота требования к надежности способа хранения содержимого документов гораздо более высоки, чем требования к надежности хранения связей/аттрибутов.

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

V>Если рассматривать содержимое файла как набор множества строк данных — то да. А если рассматривать содержимое файла как единую "строку данных", где имя файла является ключем, то ФС замечательно предоставляет все то богатство возможностей, о которых ты упомянул.
Да, совершенно верно. И это неслучайно — ФС собственно и делались с расчетом именно на такое использование.
V>Например, если мы храним документы, то ФС очень даже себя оправдывает, ибо используется в последнем качестве. Если надо прикрутить развитый документооборот, то БД может хранить всякие доп. признаки и связь документов с другими объектами БД, а сам файл может спокойно себе лежать в ФС
Нет! Вот так делать нельзя. Точнее, не стоит. Потому что никаких гарантий целостности для такого хранилища дать невозможно.
V>. Причем, ФС можно настроить так, чтобы избежать несанкционированного доступа вне рассматриваемой системы путем раздачи всяких прав.
Это не решает проблемы. Минимальный сбой в программе — и пошло рассогласование. ACID рулит! Для файлопомойки это не очень страшно. Для системы документооборота — кошмар. Я могу годами думать, что у меня важный договор лежит в папке Х. А он уже давно убит, и вместо него лежит письмо от спамера. Вот она радость-то!
V>Более того, потери базы, как видно из форумов, случаются пока гораздо чаще, чем потери файлов.
Интересный такой взгляд. Я вот не уверен. Хотя, если читать форумы по СУБД, то вряд ли там будут сильно жаловаться на битые файлы (хотя repair офиса народ делает регулярно).
Просто важные данные как правило хранят именно в СУБД, а неважные вопросов "как восстановить" не вызывают.
V>Более того, файлы зачастую можно хоть как-то восстановить,
Это как это ты собрался восстанавливать файл без копии? Или ты имеешь в виду перенабить с клавиатуры?
V>а БД — только из резервной копии. А в случае документооборота требования к надежности способа хранения содержимого документов гораздо более высоки, чем требования к надежности хранения связей/аттрибутов.
Очень интересно. Мне кажется, что у тебя не вполне корректные представления о надежности СУБД по сравнению с надежностью ФС.

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

S> Вернее Двухнаправленный Список (В пику Sinclair про однонаправленные итераторы)
Элементы, как правило, все-таки в направленый, но это уже вопрос реализации...

S>Не за каждой записью, а при переходах между страницами.
Опять-таки вопрос реализации. На практике обычно связывают и страницы и элементы, связь между элементами позволяет во-первых, не соблюдать физический порядок элементов при хранении, а во-вторых, реализовать предикатные блокировки, о чем я говорил выше.

S> Но при этом ненужно хранить состояние, если оно меняется то при переходах нужно его востанавливать.
Состояние чего? Тут я не успеваю за полетом твоей мысли...

S>Хотя версионность и здесь поможет
Версионность-то здесь причем? Это уже совсем из другой оперы.