Отслеживание местоположения страниц
Механизмы отслеживания местоположения страниц в файловых системах и системах баз данных заметно отличаются. В файловых системах страницы данных или экстенты (run) смежных страниц отслеживаются в страницах указателей (pointer page). При перемещении индивидуальной страницы может потребоваться разбиение экстента. В любом случае страницу указателей приходится модифицировать и затем записывать.
В системах баз данных большая часть данных хранится в индексах на основе B-дерева, включая кластеризованные (первичные, не избыточные) и некластеризованные (дополнительные, избыточные) индексы на таблицах, материализованные представления и каталоги баз данных. С использованием B-деревьев просто и эффективно представляются битовые индексы, поколоночные хранилища таблиц и совместно кластеризованные таблицы со связью «один-ко-многим» []. Древовидные структуры, близкие к B-деревьям, также используются для хранения BLOB’ов и близки к структурам хранения некоторых файловых систем [,].
Для B-деревьев перемещение отдельной страницы может стоить очень дорого или очень дешево. Наиболее эффективные механизмы обычно обнаруживаются в утилитах дефрагментации и реорганизации. Стоимость или эффективность перемещения страниц зависит от двух аспектов реализации B-дерева: поддержки указателей на соседние страницы и журнализации для целей восстановления.
Во-первых, если в каждой странице B-дерева поддерживаются ссылки на соседние страницы, то при перемещении одной страницы требуется обновление двух соседних страниц, а также родительского узла. Если же указатели на соседей являются логическими, основанными на использовании «ограждающих ключей» (fence key), то при перемещении страницы нужно обновлять только страницу-предка []. Если родительская страница находится в основной памяти, возможно, даже зафиксирована в буферном пуле, то фиксация нового местоположения выполняется подобно обновлению таблицы преобразования адресов, располагающейся в основной памяти. Операция изменения указателя в родительской странице журнализуется в журнале восстановления, но нет нужды немедленно выталкивать журнал в стабильную память, поскольку это изменение является всего лишь структурным, не изменяющим содержимое базы данных.
Во-вторых, в системах баз данных журнализуются изменения физической базы данных, и в предельном случае в журнал попадает содержимое как удаленной, так и заново созданной страницы. Таким образом, при неэффективной реализации при каждом перемещении одной страницы данных из одного места в другое заполняются две страницы журнала. При более эффективной реализации журнализуются только действия, связанные с новым размещением страницы данных, а старая страница вместе со своим содержимым не освобождается до тех пор, пока новое содержимое не будет надежно записано на новое место []. Другими словами, при перемещении страницы из одного местоположения (например, в персистентной флэш-памяти) в другое местоположение (например, на диске) требуется записать в журнал восстановления всего лишь несколько байт.
Файловые системы и системы баз данных различаются эффективностью операций обновления, допускаемой журналом восстановления. В файловой системе новое положение страницы должно быть сохранено как можно быстрее путем записи нового содержимого страницы указателей. В системе баз данных нужно всего лишь добавить в буфер журнала одну или несколько коротких записей. Таким образом, накладные расходы перемещения страницы в файловой системе состоят в записи всей страницы указателей с использованием произвольного доступа, в то время как в системе баз данных в буфер журнала добавляется запись из нескольких десятков байт, которая, в конце концов, будет записана с использованием крупных операций последовательной записи.
Если бы в файловой системе флэш-память использовалась как персистентное хранилище данных, то перемещение страницы между местоположением в флэш-памяти и местоположением на диске приводило бы к дополнительным существенным накладным расходам. Поэтому, чтобы избежать этих накладных расходов, большинство разработчиков файловых систем, вероятно, предпочтет использовать флэш-память, как расширение буферного пула, а не как расширение диска.
Однако в системе баз данных имеются встроенные механизмы, позволяющие легко отслеживать перемещения страниц.Эти механизмы свойственны структуре данных, являющейся «рабочей лошадкой» систем баз данных, – индексам на основе B-деревьев. По сравнению с файловыми системами, эти механизмы обеспечивают эффективные перемещения страниц, при каждом из которых требуется только часть последовательной операции записи (в журнале восстановления), а не целая операция записи с произвольным доступом.
Кроме того, механизмы баз данных являются надежными. Если при перемещении страницы произойдет отказ, то база данных будет восстановлена по журналу, в то время как для файловой системы потребуется полная проверка во время перезапуска.
