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

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

E>>>Это справедливо только для одной операции -- открытия файла по точно известному имени. Но ведь это не единственная операция. Файлы создаются и удаляются. Причем создаваться и удаляться они могут пачками. А модификация большого индекса (даже в случае с B+ деревьями) может быть не такой уж и дешовой операцией. Особенно при некоторых стечениях обстоятельств (например, если имена файлов будут образовывать монотонно возрастающию ключи).

S>>Это почему???

E>Что именно "почему"?

E>Частые ребалансировки B+ дерева, имхо, это не дешевая операция (расчепления и объединения страниц).
Как на это влияет (монотонно возрастающию ключи) ????
Все зависит от средней наполняемости выставленной разработчиком. Чем она выше тем выше скорость поиска, и ниже вставки (удаления). Монотонно возрастающие не влияют на количество балансировок.

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

Q>Я не пойму, вы что пытаетесь доказать? Что создатели ФС идиоты, неспособные догадаться о таких элементарных вещах?

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

Q>Опять же, объясните пожалуйста, с чего поиск по произвольной маске должен работать одинаково быстро на любом количестве файлов. Приведите алгоритм, который позволял бы такое делать и при этом давал бы не более O(log N) на добавление и удаление.

Я думаю, здесь случилось недопонимание. Я не говорил о скорости выборки файлов по маске на уровне файловой системы. Я говорил о том, что если какой-нибудь Ruby скрипт будет загружать в память и сортировать имена 10000 файлов, то это будет гораздо быстрее, чем загружать в память и сортировать имена 1M файлов. Хотя бы просто из-за количества объектов, которые придется создать в Ruby скрипте.

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

E>>Частые ребалансировки B+ дерева, имхо, это не дешевая операция (расчепления и объединения страниц).
S>Как на это влияет (монотонно возрастающию ключи) ????
S> Все зависит от средней наполняемости выставленной разработчиком. Чем она выше тем выше скорость поиска, и ниже вставки (удаления). Монотонно возрастающие не влияют на количество балансировок.

Разве?
Я думал, что для деревьев самым плохим сценарием является постоянный рост в одну сторону. Ведь тогда нужно постоянно делать перебалансировку дерева, чтобы дерево оставалось сбалансированным.
В случае B+ деревьев, как мне кажется, монотонно возрастающие ключи будут приводить к тому, что последняя листовая страница будет быстро заполняться, что потребует заполнять ее родительскую страницу и т.д. В результате дерево будет постоянно увеличиваться в своей глубине при том, что ранее выделенные листовые страницы не изменяются. Хотя количество перебалансировок будет гораздо меньше, чем с бинарными деревьями (за счет большего количества ключей на странице), но все равно перебалансировки будут.

Но вполне могу и заблуждаться. Настаивать не буду.

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

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

E>>>Частые ребалансировки B+ дерева, имхо, это не дешевая операция (расчепления и объединения страниц).
S>>Как на это влияет (монотонно возрастающию ключи) ????
S>> Все зависит от средней наполняемости выставленной разработчиком. Чем она выше тем выше скорость поиска, и ниже вставки (удаления). Монотонно возрастающие не влияют на количество балансировок.

E>Разве?
E>Я думал, что для деревьев самым плохим сценарием является постоянный рост в одну сторону. Ведь тогда нужно постоянно делать перебалансировку дерева, чтобы дерево оставалось сбалансированным.
E>В случае B+ деревьев, как мне кажется, монотонно возрастающие ключи будут приводить к тому, что последняя листовая страница будет быстро заполняться, что потребует заполнять ее родительскую страницу и т.д. В результате дерево будет постоянно увеличиваться в своей глубине при том, что ранее выделенные листовые страницы не изменяются. Хотя количество перебалансировок будет гораздо меньше, чем с бинарными деревьями (за счет большего количества ключей на странице), но все равно перебалансировки будут.

На количество перебалансировок это влиять не будет (их будет даже меньше в зависимости от тактики хранения), да не забудем о кэшировании страниц, что для ФС лимитирующей стадией

E>Но вполне могу и заблуждаться. Настаивать не буду.

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

M>Я просто к тому, что совершенно непонятны страдания Andrei N.Sobchuck по этому поводу..
M>Очевидно, что объектный API там будет, а что там внизу лежит — дело десятое.

Так если б так было, а то ж "уши" торчат с низу на верх.

M>Вот, кстати, по поводу "А они за основу взяли реляционку " мой любимый пример. В 2005м сиквеле ребята решили реализовать поддержку XML и XQuery.

XML вроде ж дерево, значения — строки. Имхо, это не катит на "хранилище объектов". Возможно это и объясняет тот факт, что каждый производитель БД, делает поддержку XML просто пользуясь своим хранилищем. От Berkley DB до всяких SQL серверов. Кроме того, у них наверняка стоял вопрос интеграции со всем остальным хозяйством, например оптимизатором.

Кстати, от ссылочки на детали я бы не отказался, а то инфа с 2004 года

Автор(ы): Алексей Ширшов
Дата: 16.10.2004
Третья часть статьи рассказывает о поддержке XML в готовящейся к выходу версии MS SQL Server. Рассматриваются особенности применения типа данных XML, поддержка XQuery и многие другие вопросы.

наверняка устарела:

Хранение XML-типа

Мне было очень интересно узнать, каким образом SQL Server хранит XML-тип. К сожалению, в документации об этом нет ни слова, и вряд ли положение изменится к публичной бете. Вот что я выяснил из собственных экспериментов и общения с разработчиками.

XML-тип сохраняется как большой объект (lob — large object) в бинарном формате, структура которого неизвестна, но точно можно сказать, что она линейна. Т.е. сохраняется относительный порядок узлов в документе – атрибуты следуют после элемента, к которому они принадлежат, дочерние элементы следуют после атрибутов, и последующие элементы (элементы того же уровня) – после дочерних элементов.

Для осуществления запроса XQuery SQL Server каждый раз выполняет преобразование этой линейной структуры в реляционную – в таблицу узлов (node table). Таблица узлов более формализована и понятна, однако занимает в несколько раз (даже на порядки) больше места. Любой запрос XQuery трансформируется в SQL запрос к этой таблице.

eao197 wrote:
> C>Давным-давно есть атомарные FS с гарантированой целостностью, а в
> C>Reiser4 атомарность умудрились сделать еще и без потери скорости.
> Кстати, ты можешь показать в описании Reiser4, где говорится, что
> Reiser4 поддерживает атомарность для нескольких изменений нескольких
> файлов сразу (т.е. чтобы изменение нескольких файлов составляло одну
> транзакцию)?
Где-то видел пост в список рассылки, где об этом говорилось, но найти не
могу. Там создавался временный namespace, в который помещались файлы,
при коммите этот неймспейс удалялся, так что все записывалось атомарно.

Более точно сейчас не вспомню.

Здравствуйте, Зверёк Харьковский, Вы писали:

ЗХ>Я, собственно, этими ссылками пытался показать, что в *nix-овом окружении, во-первых, форматы стандартны (т.е. не каждый клиент свой формат выдумывает, а есть 2-3 стандарта, а все клиенты их используют); а во-вторых, наиболее распространенный формат — Maildir, который как раз 1 сообщение/файл.

Я в юниксах не силён. Может там файловая система другая. С большим количеством файлов в одном каталоге в винде похоже проблема связана с процессом обновления времени последнего доступа к файлам. Т.е. каким-то образом, может быть из-за криво написанного софта, система обновляла время последнего доступа у всех 100к файлов при любом изменении в каталоге. Сервер от этого умирал. Вроде это можно как-то отключить на уровне операционки, но это не твой случай. В общем, с вариантом одно сообщение — один файл я бы сначала поэкспериментировал прежде чем его принимать.

Здравствуйте, Andrei N.Sobchuck, Вы писали:

ANS>Так если б так было, а то ж "уши" торчат с низу на верх.
Откуда они там торчат?

ANS>XML вроде ж дерево, значения — строки. Имхо, это не катит на "хранилище объектов".
А что катит? Просто объекты тоже дерево, поэтому с xml-ем у них много общего, больше чем с реляционными данными.
И данный пример как раз показывает, что у реляционки с просто хранением и выборкой иерархических данных проблем нет. А большего от данного движка и не требуется. Так что поводов огорчаться из-за наличия внизу реляционного движка нету, скорее радоваться надо, что стоит отлаженный и проверенный временем механизм...

ANS> Возможно это и объясняет тот факт, что каждый производитель БД, делает поддержку XML просто пользуясь своим хранилищем.
Ресурсы MS вполне позволили бы создать совершенно самостоятельный движек для работы с XML-ем если бы это оказалось заметно эффективнее, сначала они так и собирались делать иначе бы не копали в сторону иерархических хранилищ...

ANS>Кстати, от ссылочки на детали я бы не отказался
ORDPATHs: Insert-Friendly XML Node Labels

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

E>Я думал, что для деревьев самым плохим сценарием является постоянный рост в одну сторону.
Не для всех..

E>Ведь тогда нужно постоянно делать перебалансировку дерева, чтобы дерево оставалось сбалансированным.
B+ всегда сбалансировано, у них проблема с расщеплением страниц при росте, но тут есть алгоритмы наработанные десятилетиями.

E>В случае B+ деревьев, как мне кажется, монотонно возрастающие ключи будут приводить к тому, что последняя листовая страница будет быстро заполняться, что потребует заполнять ее родительскую страницу и т.д.
Ни к чему страшному это не приведет, B+ растет не вниз, а вверх, поэтому перебалансировки не происходит. Более того, если дерево "знает", что вставка монотонна, то и расщепления страниц можно избежать, так что в некоторых случаях рост в одну сторону выгоднее.
Иными словами, сама по себе монотонная вставка B+ не страшна, но тут есть другая проблема, если вставка происходит из нескольких параллельных потоков, то последняя страница оказывается перманентно заблокированной и возникает очередь на вставку. И вот это уже может серьезно повлиять на эффективность вставки, если критична именно вставка из параллельных потоков.
Но это все высокие материи, не думаю что ФС столкнется с подобными сценариями, все-таки на данный момент СУБД и ФС решают несколько разные задачи.

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

IT>Т.е. каким-то образом, может быть из-за криво написанного софта, система обновляла время последнего доступа у всех 100к файлов при любом изменении в каталоге. Сервер от этого умирал.

??? Почему должно минятся время доступа у файлов при изменении в каталоге (создание, удаление файлов?)?

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

E>>Ведь тогда нужно постоянно делать перебалансировку дерева, чтобы дерево оставалось сбалансированным.
M>B+ всегда сбалансировано, у них проблема с расщеплением страниц при росте,

Конечно всегда сбалансированно, ведь это достигается путем расщепления и слияния страниц в нужные моменты времени. Об этом я и говорил.

E> но тут есть алгоритмы наработанные десятилетиями.

Какие? (Не сарказм, действительно интересно).

E>>В случае B+ деревьев, как мне кажется, монотонно возрастающие ключи будут приводить к тому, что последняя листовая страница будет быстро заполняться, что потребует заполнять ее родительскую страницу и т.д.
M>Ни к чему страшному это не приведет, B+ растет не вниз, а вверх, поэтому перебалансировки не происходит. Более того, если дерево "знает", что вставка монотонна, то и расщепления страниц можно избежать, так что в некоторых случаях рост в одну сторону выгоднее.

Можно ли на эту тему подробнее?

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

E>Какие? (Не сарказм, действительно интересно).
В данном случае предельно простые.. Страница при переполнении разбивается примерно на 2/3 и треть переносится на новую.
Просто поинт в том, что содной стороны расщепление страниц в B+ это действительно одно из самых узких мест, но с другой это узкое место вылизывали десятилетиями, потому как в реляционках это основной механизм.

E>Можно ли на эту тему подробнее?
При переполнении страница расщепляется на две неравные части, при этом меньшая часть переносится на вновь созданную страницу. Таким образом на старой странице создается некоторый запас свободного места для последующих вставок, чтобы небыло необходимости расщиплять страницу при каждой вставке в середину.
Но, если, например, поле в БД автоинкрементное, то можно гарантировать, что каждое следующее значение будет больше/меньше предыдущего, а значит вставки в середину страницы не будет, а значит и разбивать страницу не надо, нет необходимости резервировать пустое место для вставки в середину, так как вероятность этого крайне мала. При переполнении просто создается новая страница и данные пишутся туда, а старая страница остается заполненой на 100% (к слову это еще и эффективность выборки увеличивает).
При этом если все-таки происходит вставка в середину, ничто не мешает таки расщепить страницу по стандартным правилам, так что тут все упирается в способность пишущего движка распознать инкрементную вставку.

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

M>Просто поинт в том, что содной стороны расщепление страниц в B+ это действительно одно из самых узких мест

По-моему, сщепление на порядок уже

Здравствуйте, Andrei N.Sobchuck, Вы писали:

ANS>??? Почему должно минятся время доступа у файлов при изменении в каталоге (создание, удаление файлов?)?

Я не знаю

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

IT>По-моему, сщепление на порядок уже
В смысле дефрагментация? Ну она зато существенно реже и не так актуально делать ее прям щас.

Merle,

> ПК> система заведомо более устойчива к разнообразным нарушениям целостности данных

> Вот это непонятно. Как раз тут основные пролемы:
> — Запись не атомарна, можно добавить метаданные, а запись конкретного файла с сообщением по каким-то причинам не пройдет.

Если критичные для работы метаданные (индексы и т.п.) могут быть восстановлены из самих файлов (что по большей части имеет место быть в случае e-mail), то эта проблема не существенна. Я говорил немного о других проблемах, когда нарушается целостность файлов с данными: вирусы/антивирусы, аппаратные и программные сбои и т.п. Последнее на практике имеет заметно большее значение.

> — Конкретное сообщение грохнется, а метаданные останутся.

Это легко диагностируемые и поправимые нарушения, в отличие от "битых" файлов баз данных.

VD>Дык зависит от задачи. И терминалогии. Напиример, исходники в БД хранить явно неразумно. Тут лучше подойдут файлы и сорс-контрол. А финансовую информацию логично хранить в БД, так как ее при этом проще анализировать.

Насколько я понимаю VSS для 2005 студии хранит исходники как раз в SQL Server

IT,

> С большим количеством файлов в одном каталоге в винде похоже проблема связана с процессом обновления времени последнего доступа к файлам.

Один файл на каждое собщение вовсе не означает, что все файлы будут "свалены" в одном каталоге. Скажем, та же Опера хранит сообщения в следующей иерархии: account/year/month/day/messageid.mbs Раньше было так: account/year-month.mbs

Здравствуйте, Павел Кузнецов, Вы писали:

ПК> Я говорил немного о других проблемах, когда нарушается целостность файлов с данными: вирусы/антивирусы, аппаратные и программные сбои и т.п. Последнее на практике имеет заметно большее значение.
Ну, вот как раз практика борьбы с такими проблемами, в БД вырабатывалась годами... Online бакапы, стандартные процедуры восстановления, определение сбоя, контроль целостности. Все это уже написано и работает, а на ФС придется либо писать самому, либо забить и тогда есть вероятность потерять файл.

ПК>Это легко диагностируемые и поправимые нарушения, в отличие от "битых" файлов баз данных.
Хм. Как раз битый файл в БД и диагностируется и восстанавливается, причем процедура совершенно стандартная, а вот битый файл просто в ФС скорее всего окажется утерянным навсегда. Другое дело, если по условиям задачи его не жалко и все навороты БД не нужны... Но если надежность все же необходима, то БД тут заведомо надежнее.

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

ANS>>Так если б так было, а то ж "уши" торчат с низу на верх.
M>Откуда они там торчат?

Торчат из "реляционки", а проявляется это в модели данных WinFS, а именно ScalarType, NestedType, Relationship. Думаю всё это до боли знакомо людям использовавшим ORM.
Может его уже как-то и причесали, потому что старые примеры удручают:

  // Add first person to the household
  HouseholdMemberData hhmd = new HouseholdMemberData (ctx);
  hhmd.Name = p1.DisplayName;
  hhmd.Target_Key = p1.ItemID_Key;
  h.HouseholdMembers.Add (hhmd);

  // Add second person to the household
  hhmd = new HouseholdMemberData (ctx);
  hhmd.Name = p2.DisplayName;
  hhmd.Target_Key = p2.ItemID_Key;
  h.HouseholdMembers.Add (hhmd);

Тьфу.

ANS>>XML вроде ж дерево, значения — строки. Имхо, это не катит на "хранилище объектов".
M>А что катит? Просто объекты тоже дерево, поэтому с xml-ем у них много общего, больше чем с реляционными данными.

Ну, всё же не дерево, а граф с циклами. Второй момент — в "объектах" значениями м.б. не только строки.

M>И данный пример как раз показывает, что у реляционки с просто хранением и выборкой иерархических данных проблем нет. А большего от данного движка и не требуется. Так что поводов огорчаться из-за наличия внизу реляционного движка нету, скорее радоваться надо, что стоит отлаженный и проверенный временем механизм...

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

ANS>> Возможно это и объясняет тот факт, что каждый производитель БД, делает поддержку XML просто пользуясь своим хранилищем.
M>Ресурсы MS вполне позволили бы создать совершенно самостоятельный движек для работы с XML-ем если бы это оказалось заметно эффективнее, сначала они так и собирались делать иначе бы не копали в сторону иерархических хранилищ...

Во-первых, тут уже приводились аргументы за то, что у МС не хватает ресурсов на исполнение всех данных обещаний. Во-вторых, написать самостоятельный движок и я могу , а вот прозрачно и с минимальным оверхедом интегрировать его... Так что далеко не факт, что такое решение приняли из-за его идеальности.