рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

Средства ускорения доступа к данным

Средства ускорения доступа к данным - раздел Электроника, Тема 1. Обработка данных средствами электронных таблиц Современным Субд Приходится Оперировать Огромными Массивами Информации, Объем...

Современным СУБД приходится оперировать огромными массивами информации, объемы которых достигают порой десятков терабайт. Выполняя запросы тысяч пользователей, они должны обеспечить небольшое, не более нескольких секунд, время отклика. СУБД не сможет эффективно работать в таких условиях, не используя методов ускорения выборки данных. Цель этих
методов – избежать полного перебора строк таблиц БД при выполнении реляционных операций, например, при соединении отношений или поиске строк, удовлетворяющих условию.

В современных СУБД используются два основных метода ускорения доступа к данным: индексирование и хеширование. Эти методы обеспечивают лучшее по сравнению с остальными время поиска и модификации таблиц БД.

Метод индексирования основан на использовании индексов. Индекс отношения очень похож на предметный указатель книги. В таком указателе приведен список упорядоченных по алфавиту терминов, которые встречаются в книге. Каждому термину сопоставлена страница или страницы, где он встречается. Обычно предметный указатель занимает не более нескольких страниц.
Если нам требуется найти место в книге, где термин раскрывается, мы находим его в предметном указателе, это легко сделать – указатель невелик, кроме того, все термины там упорядочены по алфавиту. Затем мы читаем номер страницы, соответствующий термину, раскрываем книгу на ней и находим нужный нам абзац. Если бы предметный указатель отсутствовал, нам пришлось бы пролистывать все страницы, чтобы найти интересующее нас место, и мы бы потратили значительно больше времени.

Индекс базы данных – не листы бумаги, это – специальная структура данных, создаваемая автоматически или по запросу пользователя. В целом работа с ним выглядит так же, как и с предметным указателем. Разница лишь в том, что СУБД все делает автоматически, пользователь может даже не знать, что она использует индекс. В книге приводится предметный указатель слов, в БД для формирования индекса может быть использован любой атрибут отношения, в том числе и составной. В индексе значения атрибута хранятся упорядоченно (по возрастанию или убыванию), каждому значению соответствует указатель на строку отношения, которое его содержит (аналог номера страницы в предметном указателе). Индекс занимает значительно меньший, чем таблица, объем, поэтому даже полный перебор значений в нем потребует меньше времени, чем считывание и поиск информации в отношении. Кроме того, значения в индексе хранятся упорядоченно, что позволяет резко ускорить поиск нужной строки. Индексы позволяют выбирать строки отношений, значения индексируемого атрибута которых принадлежит некоторому заданному интервалу.

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

Еще один интересный подход, применяемый для повышения эффективности доступа к данным, – хеширование (hashing). Для метода хеширования, к сожалению, нет житейского аналога, поэтому объяснить его «на пальцах» вряд ли получится. Основная идея хеширования – организация ассоциативной памяти для хранения строк таблицы с определением места строки в таблице по значениям одного или нескольких ее ключевых атрибутов. Место строки вычисляется хэш-функцией, аргументы которой – значения атрибутов, а результат – целое число в диапазоне номеров строк таблицы. Идеальная хэш-функция должна давать разные значения номеров строк для разных ключевых атрибутов. Однако построить такую хэш-функцию – дело трудоемкое и не всегда возможное.

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

f(k) = k mod p,

где f – хэш-функция, k – целочисленный атрибут, а р – простое число.

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

Доступ к данным при хешировании производится так. В начале работы с БД таблица состоит из пустых строк. Когда строка с данными заносится в таблицу, вычисляется значение хэш-функции для ее атрибутов, и результат трактуется как номер строки отношения, в которую она должна быть записана.
Если эта строка уже занята, то по некоторому алгоритму производится проверка следующих строк таблицы до тех пор, пока не будет обнаружено свободное место (при этом, как правило, считается, что таблица имеет кольцевую структуру). В это место и помещается записываемая строка. Для поиска данных используется аналогичный алгоритм. Сначала вычисляется значение хэш-функции для требуемого значения ключевого атрибута и проверяется строка таблицы, номер которой вычислен хэш-функцией. Если значение атрибута, по которому происходит доступ, соответствует значению ключа строки, то поиск заканчивается. В противном случае проверяются следующие строки таблицы до обнаружения кортежа с нужным значением или пустой строки. Пустая строка свидетельствует об отсутствии кортежа с нужным значением ключа в таблице – процедура занесения данных обязательно бы использовала ее, если бы требуемый кортеж существовал.

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

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

– Конец работы –

Эта тема принадлежит разделу:

Тема 1. Обработка данных средствами электронных таблиц

Предисловие... Тема Обработка данных средствами электронных таблиц... Область применения Основные понятия электронных таблиц...

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Средства ускорения доступа к данным

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

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

Ячейки и их адресация
На пересечении столбцов и строк образуются ячейки таблицы. Они являются минимальными элементами хранения данных. Обозначение отдельной ячейки сочетает в себе номера столбца и строки (в этом

Общая характеристика интерфейса MS Excel
Среди основных интерфейсных элементов окна (см. рис 1.1) могут быть названы: • строка меню; • панели инструменто

Технология ввода данных в MS Excel
Как уже отмечалось ранее, ячейка предназначена для того, чтобы хранить различные значения различных типов. Она имеет уникальный адрес, может иметь имя, может иметь и менять значения. Ячейк

Формулы
Вычисления в таблицах программы Excel осуществляются при помощи формул. Каждая формула начинается с символа равно (=). Формула может содержать числовые константы, ссылки на ячейки и

Автозаполнение формулами
В ходе автозаполнения во внимание принимается характер ссылок в формуле: относительные ссылки изменяются в соответствии с относительным расположением копии и оригинала, а абсолютные ссылки остаются

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

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

Модели данных
Набор принципов, определяющих организацию логической структуры хранения данных в базе, получил название модели данных. Модели баз данных определяются тремя компонентами: • допустимо

Язык запросов
База данных бесполезна, если отсутствуют средства доступа к информации в ней. Для получения информации из БД пользователи направляют СУБД-запросы. СУБД обрабатывает их и отправляет результаты

Программные системы управления базами данных
Кратко остановимся на конкретных программных продуктах, относящихся к классу СУБД. На самом общем уровне все СУБД можно разделить на: • профессиональные, или промышленные; • персо

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

Объекты базы данных
Кроме таблиц база данных может содержать и другие типы объектов. Привести полную классификацию возможных объектов баз данных затруднительно, поскольку каждая система управления базами данных м

Режимы работы с базами данных
Обычно с базами данных работают две категории исполнителей. Первая категория – проектировщики. Их задача состоит в разработке структуры таблиц базы данных и согласовании ее с заказчиком. Кро

Разработка схемы данных
Выяснив основную часть данных, которые заказчик потребляет или поставляет, можно приступать к созданию структуры базы, то есть, структуры ее основных таблиц. 1. Работа начинается с составл

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

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

Структурное программирование
С появлением массовых ЭВМ 3-го поколения устаревшая технология программирования оказалась основным фактором, сдерживающим развитие и распространение компьютерных (информационных) технологий, что по

Нисходящее проектирование
Метод основан на идее уровней абстракции, которые становятся уровнями модулей в разрабатываемой программе. На этапе проектирования строится схема иерархии, изображающая эти уровни. Схема иерархии п

Концепция модульного программирования
Модуль – основа концепции модульного программирования. Каждый модуль в функциональной декомпозиции представляет собой «черный ящик» с одним входом и одним выходом. Функциональная декомпозиция задач

CASE-системы
За последнее десятилетие в области средств автоматизации программирования сформировалось новое направление под общим названием CASE-технология (Computer Aided Software Engineering-

Индустрия искусственного интеллекта
При создании программных продуктов возникает проблема, связанная с отсутствием полного взаимопонимания между заказчиком (пользователем) и исполнителем программного продукта, возникающее из-за отсут

Данные и знания
При изучении интеллектуальных систем традиционно возникает вопрос – что же такое знания и чем они отличаются от данных. Данные – это отдельные факты, характеризующи

Модели представления знаний
Существуют десятки моделей (или языков) представления знаний для различных предметных областей. Большинство из них может быть сведено к следующим классам: • продукционные модели;

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

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

Целочисленные типы данных
Целочисленные типы данных занимают в памяти компьютера от 1 до 4 байт (табл 6.1). Таблица 6.1.Целочисленные типы данных Тип Диапазон значени

Вещественные типы данных
Вещественные типы данных занимают в памяти компьютера от 4 до 10 байт (табл. 6.2). Таблица 6.2. Вещественные типы данных Тип Диапазон значен

Строковый тип
Строка – последовательность символов (до 255). Пример Var Str: string; {будет зарезервировано 256 байт} Name: string[25]; {будет зарезервировано 26 байт}

Логические выражения, выражения отношения
В Паскале есть шесть операций отношения (=, <>, <, >, <=, >=), позволяющих сравнивать между собой результаты арифметических выражений. По обе стороны операции отношения должны быт

Цикл. Виды Циклов
Циклом называется многократное повторение последовательности действий. Телом же цикла будем называть те самые действия, которые нужно многократно повторять. Повторять одни и те же действия

Цикл «С параметром».
В данном случае параметром будет являться целочисленная переменная, которая будет изменяться на единицу при каждой итерации цикла. Таким образом, задав начальное и конечное значения для такой перем

Массивы
До сих пор мы рассматривали переменные, которые имели только одно значение, могли содержать в себе только одну величину определенного типа. Вы знаете, что компьютер предназначен в основном

Одномерные массивы
Описание типа линейного массива выглядит так: Type <Имя типа>=Array [<Диапазон индексов>] Of <Тип элементов>; В качестве индексов могут выступать переменные любы

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

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

Компьютерных сетей
  Значительное повышение эффективности ЭВМ может быть достигнуто объединением их в вычислительные сети (ВС). Под вычислительной сетьюпонимают соединение двух и

Основные показатели качества ИВС
1. Полнота выполняемых функций. Сеть должна обеспечивать выполнение всех предусмотренных для нее функций и по доступу ко всем ресурсам, и по совместной работе узлов, и по реализации всех про

Виды информационно-вычислительных сетей
Информационно-вычислительные сети (ИВС) в зависимости от территории, ими охватываемой, подразделяются на: · локальные (ЛВС или LAN – Local Area Network); · региональные (РВС или M

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

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

Канальный уровень
Канальный уровень решает две задачи. Первая задача – определение доступности среды передачи данных. Эта задача решается в сетях с разделяемой средой передачи данных, когда в конкретны

Сетевой уровень
На сетевом уровне решаются вопросы объединения сетей с разными топологиями, с разными принципами передачи данных между конечными узлами для образования единой транспортной системы. Здесь сет

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

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

Маршрутизаторы и коммутирующие устройства
Основным назначением узлов коммутации является прием, анализ, а в сетях с маршрутизацией еще и выбор маршрута; и отправка данных по выбранному направлению. В общем случае узлы коммутации включают в

Аналоговые модемы
Первоначально аналоговый модем был предназначен для выполнения следующих функций: · преобразование широкополосных импульсов (цифрового кода) в узкополосные аналоговые сигналы – при передач

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

Сетевые карты
Вместо модема в локальных сетях можно использовать сетевые адаптеры (сетевые карты, network adapter, net card), выполненные в виде плат расширения, устанавливаемых в разъем материнской платы

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

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

Тема 11. Локальные вычислительные сети
  Локальной вычислительной сетью (ЛВС)называют сеть, элементами которой являются вычислительные машины (в том числе мини- и микрокомпьютеры), терминалы, связна

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

Базовые технологии локальных сетей
Для упрощения и удешевления аппаратных и программных средств в локальных сетях чаще всего применяются моноканалы, используемые совместно всеми компьютерами сети в режиме разделения времени (второе

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

Построение локальных сетей средствами сетевого уровня
Применение средств только канального уровня с использованием таких устройств, как концентраторы и коммутаторы, для построения больших вычислительных сетей имеет существенные ограничения и недостатк

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

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

Програмное обеспечение работы в Интернете
Для работы в Интернете имеются как универсальные программы (программные комплексы), обеспечивающие доступ к любой службе Интернета, так и специализированные программы, обычно предоставляющие более

Адресация и протоколы в Интернете
Компьютер, подключенный к Интернету, называется ХОСТОМ. Для идентификации каждого хоста в сети имеются две системы адресов, всегда действующие совместно. IР-адрес. Первая

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

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

Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • Популярное
  • Облако тегов
  • Здесь
  • Временно
  • Пусто
Теги