40125

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

Доклад

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

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

Русский

2013-10-15

78 KB

19 чел.

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" - резать, измельчать). Имея такую функцию можно вычислить адрес записи в файле по заданному ключу поиска. В общем случае ключевые данные, используемые для определения адреса записи организуются в виде таблицы, называемой хеш-таблицей.

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

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

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

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

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

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


 

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

46589. Методы и средства предупреждения пожара, взрыва и обеспечения противопожарной защиты на объекте экономики 21.1 KB
  Для ограничения развития пожара в зданиях сооружениях предусматривают противопожарные преграды: противопожарные стены перегородки перекрытия зоны тамбурышлюзы двери окна люки и клапаны. В этих стенах перекрытиях и перегородках допускают устройство проемов в которых предусмотрены противопожарные двери окна ворота люки и клапана или тамбурышлюзы. Противопожарные двери могут быть НГ или ГВ. НГ двери изготовляют из металлического каркаса обшитого кровельной сталью.
46590. Радиационная, химическая и медико-биологическая защита населения 21.14 KB
  Она реализуется тремя способами защиты: 1 укрытие населения в защитных сооружениях; 2 рассредоточение в загородной зоне работников предприятий и других объектов экономики продолжающих трудиться в городах а также эвакуация из этих городов населения; 3 использование населением СИЗ. Щель не обеспечивает защиту людей от ОВ и БВ поэтому необходимо применение СИЗ. Применение СИЗ и медицинских СЗ. Как известно СИЗ подразделяются на СЗ органов дыхания и кожи.
46591. Реформирование системы государственной власти и законодательства 1985-1991 гг 21.17 KB
  было заменено 70 членов Политбюро 60 секретарей областных партийных организаций 40 членов ЦК КПСС. был смещен первый секретарь Московского горкома КПСС В. состоялся XXVII съезд КПСС который изменил Программу партии. На январском пленуме ЦК КПСС в 1987 г.
46592. Организационные основы обеспечения ОТ на предприятиях 21.25 KB
  Они вытекают из обязанностей и прав по ОТ работодателя и работника которые регламентируются КЗоТом РФ и Основами законодательства РФ об ОТ далее Основами. 3 Основ закрепляет признание и обеспечение приоритета жизни и здоровья работников по отношению к результатам производственной деятельности предприятия. 139 КЗоТ РФ основной обязанностью работодателя по ОТ является обеспечение здоровых и безопасных УТ на каждом РМ. Поэтому он обязан внедрять современные средства ТБ предупреждающие травматизм и обеспечивать санитарногигиенические...
46593. Архитектурная акустика 21.46 KB
  Термическое сопротивление. Сопротивление теплопередаче ограждающей конструкции.Требуемое сопротивление теплопередаче. Сопротивление теплопередаче.
46594. Методика преподавания на профильном уровне. Элективный курс по художественному профилю и специфика его разработки 21.48 KB
  Макаренко в своем учении выделяет несколько стадий этапов:1 стадия становление коллектива стадия первоначального сплочения.актив поддерживает требования педагога и сам предъявляет их к членам колва руководствуясь своими понятиями о том что приносит пользу а что ущерб интересам коллектива. Если активисты правильно понимают потребности коллектива то они становятся надежными помощниками педагога.Происходит стабилизация структуры коллектива.
46595. Мовне законодавство в Україні 21.5 KB
  Мовне законодавство в Україні. В Україні державна мова закріплена першою частиною десятої статті Конституції України відповідно до якої державною мовою в Україні є українська мова. Окрім того вживання мов в Україні регулюється Законом Української РСР Про мови в Українській РСР . Мовна ситуація в Україні є доситьтаки суперечливою і законодавство зовсім її не спрощує.
46596. Пряме й переносне значення слова. Вияви полісемії в різностильових текстах 21.5 KB
  Пряме й переносне значення слова. Пряме значення слова це дефініція слова яка безпосередньо вказує на його співвідношення з тією чи іншою ознакою об'єктивної дійсності як це історично закріпилося у свідомості мовців. Це первинне значення слова. Переносне значення слова це одне із значень слова яке виникло внаслідок перенесення одних ознак предметів чи явищ на інші.
46597. Синонімія, види синонімів. Роль синонімів у різностильових текстах 21.5 KB
  Синонімія це сукупність синонімів тієї чи іншої мови а також розділ науки про мову у якому вивчаються синоніми як одиниці мови. Синоніми це слова однієї частини мови що мають близьке лексичне значення але відрізняються за формою. Традиційно виділяють загальномовні синоніми зрозумілі для кожного носія мови граний красивий; контекстуальні або авторські синоніми у конкретному тексті. Окремо виділяють абсолютні синоніми слова які мають тотожні значення лелека чорногуз сум смуток століття сторіччя.