40125

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

Доклад

Менеджмент, консалтинг и предпринимательство

Предполагается что для доступа к iой записи нужно просмотреть все i1 записи. Последовательный доступ с фиксированной длиной записи. Картинка i = 0 i 1L Если записи располагаются в оперативной памяти то это массив. Если записи расположены на диске то порядок ввода вывода данных зависит от языка программирования.

Русский

2013-10-15

78 KB

20 чел.

40. Физическая организация баз данных. Файлы: последовательные, с прямым доступом, с хеш-адресацией, индексно-последовательные, В-деревья.

Методы доступа – совокупность отношений о физической организации данных и алгоритмов выполнения.

Существуют три группы методов доступа:

  1.  Последовательные;
  2.  Индексные;
  3.  Адресные.
  4.  Последовательные методы доступа. Предполагается, что для доступа к i-ой записи нужно просмотреть все i-1 записи. Первая запись имеет фиксированный адрес имеются несколько разновидностей этого метода. Первые три характеризуются тем что данные располагаются на смежных участках памяти, остальные используют понятие списков.

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

  1.  Последовательный доступ с фиксированной длиной записи.

Картинка

Ai = A0 + (i - 1)L

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

  1.  Последовательный доступ с записями переменной длины. В этом случае каждая запись содержит значение длины записи.

  1.  Последовательный доступ с записями неопределенной длины. В этом случае в конец каждой записи помечается определенным символом.

  1.  Простой линейный список.
    •  Со встроенными указателями

Картинка

 

  •  С внешними указателями

Картинка

  1.  Циклический однонаправленный список. Связь от последней записи идет к первой, поэтому доступ можно получить к любой записи начиная с любой записи

Картинки

  1.  Двунаправленный список. Каждая запись имеет два указателя.

  1.  Индексные методы доступ. В дополнение  к основному файлу создается индексный файл, который содержит значения ключей. Индексный файл упорядочен по значению ключа.
  2.  Метод доступа с полным индексом. Используется, когда основной файл не очень велик.

Картинка

Основной файл

Индексный файл

Замечания: Если надо упорядочить исходный файл по нескольким ключам, то для него создается столько же индексных файлов. Т.к. значения вторичных ключей не уникальны, то индексный файл организуется по методу b) или c) последовательного доступа. Основной эффект с инвертированным массивом (вторичные ключи) применяется при поиске файлов по нескольким условиям. Алгоритм поиска строится так чтобы обращаться к индексным файлам. Наибольший эффект достигается тогда, когда индексный файл помещается в оперативной памяти.

  1.  Индексно-последовательный. Основной файл всегда упорядочен по первичному ключу, индексный файл содержит не на каждую запись как c) или d), а на группу или блок записей, т.е. на значение одного из ключей группы. Повторение ключей в группе недопустимо. В группе должно быть одинаковое число записей. Обычно при таком подходе индексный файл ещё меньше.

Замечание: Поскольку индексный файл также упорядочен по ключу, то к нему можно применить ту же идею и для него построить индексный файл и т.д. пока на самом верхнем уровне не окажется один. Такая структура называется В-деревом.

  1.  Адресные методы доступа. В этих методах значение ключа с помощью специальной функции преобразуется в значение адреса записей такой функции называется адресной. Существует два вида адресной функции:
    1.  Реализует взаимнооднозначное соответствие Адрес ↔ Ключ (прямой доступ).

Прямой доступ к записи. Физический адрес записи непосредственно определяется из самой записи.

  1.  Реализует однозначное соответствие Ключ ↔ Адрес (хеширование - перемешивание).

Хэширование.

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

Если множество ключей заранее неизвестно или очень велико, то от идеи однозначного вычисления адреса записи по ее ключу отказываются, а хеш-функцию рассматривают просто как функцию, рассеивающую множество ключей во множество адресов.

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

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

Существует два способа разрешения:

  •  Способ открытой адресации. Когда появляется коллизия во время добавления записей ищется свободный  участок памяти, куда помещается новая запись. При поиске записи поступают аналогично, т.е. сначала производят поиск  по адресу, а затем если запись с искомыми ключами не найдена, последовательно просматриваются остальные участки памяти.
  •  Способ цепочек. Каждая запись имеет ссылку на область переполнения, в  которую записываются цепочки коллизий.

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


 

А также другие работы, которые могут Вас заинтересовать

75908. Аграрная политика в дореволюционной России и в СССР: крепостное право и коллективизация без выдачи паспортов, община и колхоз 16.6 KB
  Крепостное право и кресьянская община. В России крестьянская община зародилась вместе с Древнерусским государством и видоизменяясь просуществовала вплоть до конца 1920х. В период Киевской Руси крестьянская община стала основной производящей единицей.
75909. В чем причины кризиса советской экономики в 1980-е гг.? Системный кризис, падение цен на нефть, нерентабельность производства, экстенсивный характер развития? Причины субъективные и объективные 15.55 KB
  Системный кризис падение цен на нефть нерентабельность производства экстенсивный характер развития Причины субъективные и объективные. Проблемы экономического развития были вызваны рядом причин: Системный кризис. В условиях догоняющего развития без демократических свобод при отсутствии гражданского общества в СССР произошла подмена цели средствами главной жертвой которой стала свобода как необходимое хотя и не единственное условие развития человека его инициативы и предприимчивости. Советская модель хозяйствования лишенная...
75910. Как характеризуют существовавшие в конце 80-х - начале 90-х программы реформ Г.Явлинский и А.Чубайс? Каковы отличия в подходах и восприятии 18.19 KB
  Российская приватизация по масштабам и объему стоящих перед ней задач принципиально отличалась от приватизации осуществленной в 1980е годы в странах Запада.Чубайс прохладно относился к приватизации однако понимал важность ее осущетсвления в рамках проведения рыночных реформ. списка литры: мы вели очень жесткую теоретическую дискуссию с Виталием Найшулем как автором концепции ваучерной приватизации приводили ему длинный список катастрофических тяжелейших последствий которые она неизбежно повлечет за собой. мне лично тема приватизации...
75911. Особенности шоковой терапии и приватизации в России 18.04 KB
  Особенности процесса приватизации происходившего в России: массовый характер приватизации вызванный высокой долей государственной собственности в стране а также стремлением ускорить процесс преобразования экономической структуры общества; значительный удельный вес неэквивалентных форм безвозмездная передача оплата не в полной мере и др. вызванный отсутствием денежных средств в частных руках; проведение особого ваучерного этапа приватизации. Целью приватизации провозглашалось создание эффективного собственника однако бесплатная...
75912. Российские экономические реформы 1990-х гг. в оценках западных исследователей: направления критики 19.84 KB
  В оценках западных исследователей: направления критики Негативная оценка результатов российских реформ общее в выступлениях экономистов Оправдывать или объяснять логику развития событий в России становится неприличным и социально опасным Российские реформы далеки от того чтобы считать их феноменально успешными Главные аргументы критиков Игнорирование китайского опыта...
75913. Понятие «модернизация». Что подразумевают под «европейской модернизацией» России? Какие исторические формы этот процесс приобретал? Можно ли считать сталинскую индустриализацию модернизацией 16.6 KB
  Что подразумевают под европейской модернизацией России Какие исторические формы этот процесс приобретал Можно ли считать сталинскую индустриализацию модернизацией Модернизация современный термин используемый для характеристики давно уже идущего в мире процесса процесса социальных изменений посредством которых менее развитые общества приобретают характеристики отличающие большинство развитых обществ. Несмотря на то что исторически многие страны в своем развитии шли бок о бок термин модернизация долгое время не использовался....
75914. Помешало ли строительство империи в России (XVIII-XIX вв.) созданию российской (русской) нации? Точки зрения Хоскинга и Миллера. Понятие нации и русского национализма в России до 1917 года 20 KB
  Усилия уходившие на сбор налогов и создание армии для нужд империи требовали подчинения практически всего населения особенно русских интересам государства и таким образом затрудняли создание общественных ассоциаций представляющих основу для национального самосознания в гражданском смысле. В России условия для национального самосознания были созданы в XVI веке изобретением традиции это дало толчок и послужило оправданием первых шагов по строительству империи но в середине XVII века само имперское государство внезапно отказалось от...
75915. Политика «коренизации» и межнациональные отношения в период создания СССР. Нациостроительство и проведение границ союзных республик 18.67 KB
  В резолюции XII съезда чётко записано: органы национальных республик и областей строились по преимуществу из людей местных знающих язык быт нравы и обычаи соответствующих народов; были изданы специальные законы обеспечивающие употребление родного языка во всех государственных органах и во всех учреждениях обеспечивающих местное национальное население и национальные меньшинства законы преследующие и карающие со всей революционной суровостью всех нарушителей национальных прав и в особенности прав национальных меньшинств. был...
75916. Трансформация представлений о морали в России 16-19 вв: общее и особенное 29 KB
  История развития морали в России начинается уже в устных и письменных произведениях Древней Руси. С принятием христианства Россия обогатилась учениями морали пришедшими к ней из Византии и объединившими в себе лучшие традиции греческой философской школы. Теория морали которую основали древнегреческие мыслители была дополнена русскими учеными разработавшими собственные оригинальные этические концепции и нравственные идеи.