Как называется иерархическая структура в информатике
Урок 4
Структура информации (простые структуры). Деревья. Графы
§4. Структура информации
Содержание урока
Иерархия (дерево)
Иерархия (дерево)
Линейных списков и таблиц иногда недостаточно для того, чтобы представить все связи между элементами. Например, в некоторой фирме есть директор, ему подчиняются главный инженер и главный бухгалтер, у каждого из них есть свои подчинённые. Если мы захотим нарисовать схему управления этой фирмы, она получится многоуровневой (рис. 1.11, а).
Такая структура, в которой одни элементы «подчиняются» другим, называется иерархией (от древнегреческого fepap%ta — священное правление). В информатике иерархическую структуру называют деревом. Дело в том, что, если перевернуть схему на рис. 1.11 вверх ногами, она становится похожа на дерево (точнее, на куст, см. рис. 1.11, б).
Дерево состоит из узлов и связей между ними (они называются дугами). Самый первый узел, расположенный на верхнем уровне (в него не входит ни одна стрелка-дуга), — это корень дерева. Конечные узлы, из которых не выходит ни одна дуга, называются листьями. Все остальные узлы, кроме корня и листьев, — промежуточные.
Из двух связанных узлов тот, который находится на более высоком уровне, называется родителем, а другой — сыном. Корень — это единственный узел, у которого нет родителя; у листьев нет сыновей.
Используются также понятия предок и потомок. Потомок какого-то узла — это узел, в который можно перейти по стрелкам от узла-предка. Соответственно, предок какого-то узла — это узел, из которого можно перейти по стрелкам в данный узел.
В дереве на рис. 1.12 родитель узла Е — это узел В, а предки узла Е — это узлы А я В, для которых узел Е — потомок. Потомками узла А (корня) являются все остальные узлы.
Типичный пример иерархии — различные классификации (животных, растений, минералов, химических соединений). Например, отряд Хищные делится на два подотряда: Псообразные и Кошкообразные. В каждом из них выделяют несколько семейств (рис. 1.13).
Конечно, на рис. 1.13 показаны не все семейства, остальные обозначены многоточиями.
В текстах иерархию часто представляют в виде многоуровневого списка. Например, оглавление книги о хищниках может выглядеть так:
Глава 1. Псообразные
Глава 2. Кошкоообразные
1 В современных файловых системах (NTFS, ext3) файл может «принад¬лежать» нескольким каталогам одновременно. При этом древовидная структура, строго говоря, нарушается.
Алгоритм вычисления арифметического выражения тоже может быть представлен в виде дерева (рис. 1.15).
Здесь листья — это числа и переменные, тогда как корень и промежуточные вершины — знаки операций. Вычисления идут «снизу вверх», от листьев — к корню. Показанное дерево можно записать так:
Самое интересное, что скобки здесь необязательны; если их убрать, то выражение всё равно может быть однозначно вычислено:
Такая запись, которая называется префиксной (операция записывается перед данными), просматривается с конца. Как только встретится знак операции, эта операция выполняется с двумя значениями, записанными справа. В рассмотренном выражении сначала выполняется умножение:
и ещё одно умножение:
и наконец, вычитание:
Для получения префиксной записи мы обходили все узлы дерева в порядке «корень — левое поддерево — правое поддерево». Действительно, сначала записана метка корня («-»), затем все метки левого поддерева, а затем — все метки правого поддерева. Для поддеревьев используется тот же порядок обхода. Если же обойти дерево в порядке «левое поддерево — правое поддерево — корень», получается постфиксная форма (операция после данных). Например, рассмотренное выше выражение может быть записано в виде
Для вычисления такого выражения скобки также не нужны, и это очень удобно для автоматических расчётов. Когда программа на языке программирования высокого уровня переводится в машинные коды, часто все выражения записываются в бесскобочной постфиксной форме и именно так и вычисляются. Постфиксная форма для компьютера удобнее, чем префиксная, потому что, когда программа доходит до знака операции, все данные для выполнения этой операции уже готовы.
Следующая страница 
Графы
Cкачать материалы урока
Что представляет собой иерархическая файловая структура? Информатика
Содержание:
На компьютере хранятся тысячи файлов. При расположении всех в одном каталоге с документами трудно работать. Для их структуризации применяется понятие «иерархическая система» или «файловая структура» (ФС), представленная в виде дерева. С ней документы можно распределять по разным иерархическим уровням, подобно тому, как растут ветви на деревьях. Рассмотрим, что она собой представляет, какие разновидности бывают.
Что такое файловая структура диска
Графическое изображение иерархической файловой структуры выглядит следующим образом.
Система управления документами выполняет ряд функций:
Разновидности
Поясним. Физически все файлы расположены на одном жёстком диске или в флеш-памяти. Для обращения к ним используется адресное пространство – указывается путь. Представим, что все документы находятся на одном диске C:\.
Для обращения к документам в одноуровневых ФС вводят название раздела, далее – его имя, например, C:\file.docx.
После буквенной метки диска ставится двоеточие, затем – обратная косая черта «\».
Логически эти файлы располагаются в различных каталогах (папках, директориях) – абстрактные структуры, логические контейнеры, применяемые для упорядочивания, структурирования и группировки документов.
Например: C:\документы\file.docx, C:\видео\сериалы\8сезон\серия5.mp4. После названия папки ставится разделитель – обратная косая черта, после имени документа – точка, затем – его расширение, обычно состоящее из трёх букв.
При описанной организации ФС документы имеют два имени:
На одном физическом диске может располагаться несколько (зависит от файловой системы) логических разделов (томов). Если этот накопитель используется для запуска операционной системы, первый его диск будет системным – хранятся файлы ОС и активным – из него «операционка» загружается. Обычно имеет буквенную метку «C». Остальные диски предназначены для пользовательских данных, по умолчанию носят буквенные метки, следующие за «С» в английском алфавите: D, E, F. A и B – зарезервированы под флоппи-дисководы, которые вышли из обихода.
Описанная ФС ускоряет поиск нужных файлов, позволяет:
Благодаря папкам мы понимаем, что в каталоге «Фильмы» находятся видеофайлы, «Фото» – фотоколлекция, в «Фото\Отпуск\2021» снимки с последнего отдыха. В каталогах «Физика» и «Химия» могут располагаться объекты с одинаковыми именами – «Лабораторная работа №1.docx».
Порядок подчинения или древовидная структура файлов формируется пользователем на всех разделах, кроме системного, где всё делают программы установки ОС и приложений. Человеку в иерархию каталогов на разделе C:\ вмешиваться не стоит.
Ныне практически каждая файловая система многоуровневая или древовидная – это рассмотренный выше метод организации хранения данных. Одноуровневая файловая структура – это устаревшая, практически не использующаяся ФС. Пример: когда в корне диска – съёмного накопителя – размещены десятки файлов без каталогов.
Особенности обращения к файлам
При открытой папке «D:\книги\учебники» можно ввести «информатика.pdf», а Проводник превратит путь в «D:\книги\учебники\информатика.pdf».
Монтирование
Организовать хранение содержимого внешних накопителей (флешек, компакт-дисков) на одном устройстве можно путём размещения отдельной автономной файловой структуры на внутреннем носителе. Её принято называть образом – это отдельный файл, в котором хранится точная цифровая копия содержимого флешки, логического или физического раздела. Создав такую копию, её монтируют в виртуальный дисковод и работают как с физическим носителем в режиме чтения. Изменять содержимое образа привычным способом нельзя.
Диск D:\ – образ, точная цифровая копия флешки.
Есть варианты объединения файловых структур разных логических либо физических накопителей в одну. После монтирования разницы между корневой и смонтированной ФС нет.
Тесты
Что это такое файловая структура диска?
Какую структуру имеет файловая система
Основные понятия иерархической модели базы данных
Иерархическая модель базы данных — что это такое в информатике
Иерархическая модель базы данных — это древовидная структура, состоящая из данных или объектов разных уровней.
Преимуществами модели являются:
Среди несовершенств выделяют:
Осторожно! Если преподаватель обнаружит плагиат в работе, не избежать крупных проблем (вплоть до отчисления). Если нет возможности написать самому, закажите тут.
Работа с иерархическими базами данных требует значительных ресурсов основной и дисковой памяти вычислительной машины. А это заметно понижает скорость считывания параметров, обработки информации.
Основные понятия, принцип построения
Между объектами иерархической базы присутствуют связи. Каждый из них может включать в себя объекты низшего уровня, быть зависимым от стоящего выше.
Если из двух объектов один расположен ближе к корню, его называют предком. Если дальше — потомком. Потомок всегда имеет только одного предка. А у предка может быть несколько потомков. При этом потомки одного уровня, имеющие единого предка, именуются близнецами или братьями.
Структурная часть
Основными элементами, информационными единицами выступают:
Экземпляр — это образование из определенных значений полей данных. Тип — поименованная совокупность составляющих сегмент типов полей.
Иерархическая модель основана на графовой форме построения: вершине графа соответствует сегмент или тип сегмента, дугам — связи «предок-потомок». Модель представляет собой связный неориентированный граф объединяющей сегменты древовидной структуры. База данных состоит из строго упорядоченного набора деревьев.
Управляющая часть
Для рассматриваемой модели разработаны языковые средства описания данных и манипулирования ими. База описывается набором операторов, определяющих структуру хранения и логику построения. При этом вариант создания связей между физическими записями определяется способом доступа, который может быть:
Описание должно содержать имя БД, способ доступа, уточнение типа сегмента в соответствии с иерархией.
Каждая база имеет один корневой сегмент. А система может включать несколько физических баз.
Операций манипулирования данными в рассматриваемой модели немного. Это поиск данных, их модификация и поиск с возможностью модификации. Но, несмотря на сравнительно небольшой набор, его вполне достаточно для корректного и эффективного управления.
Характерные особенности, какие операции можно производить
В качестве примера операций по поиску данных можно привести такие задачи, как:
Типичные операторы модификации:
Примеры поиска данных с возможностью модификации:
Особенной характеристикой иерархической базы данных является то, что она оптимизирована на чтение, а не запись. Система быстро производит поиск, выбор и представление информации пользователю, но не позволяет оперативно обновлять и заменять ее.
В сравнении с базами, построенными на основе цикла, иерархическая структура более функциональна: одна циклическая база хранит только один неизменный набор данных.
Применение иерархической структуры данных на практике
Самым простым практическим применением структуры является традиционная файловая система ОС Windows. Зайдя в знакомый всем Проводник, мы попадаем в корень и видим крупные структурные единицы: «Этот компьютер», «Сеть» и другие. Продвигаясь в направлении от корня и выбирая одну из единиц, мы переходим к папкам, затем к файлам и находим нужную информацию.
Широко известными иерархическими базами данных считаются:
К этой же категории принадлежит System 2000 от американской частной компании SAS Institute.
Если отойти от информатики, то практическое применение можно обнаружить в биологии, географии, анатомии. По принципу нисходящей ветвящейся структуры организована классификация живых организмов, выстроены объекты гидросферы, отображены разветвления нервов и кровеносных сосудов.
Прямым аналогом, отображающим свойства и основы построения иерархических баз данных, является генеалогическое дерево.
Иерархические БД
Урок 27. Информатика и ИКТ 11 класс (к учебнику Н. Д. Угриновича)
В данный момент вы не можете посмотреть или раздать видеоурок ученикам
Чтобы получить доступ к этому и другим видеоурокам комплекта, вам нужно добавить его в личный кабинет, приобрев в каталоге.
Получите невероятные возможности
Конспект урока «Иерархические БД»
На этом уроке мы с вами вспомним, что такое иерархическая структура и из каких элементов она состоит. Также рассмотрим несколько примеров иерархической базы данных.
Начнём мы с вами с рассмотрения иерархической структуры базы данных.
Иерархическая структура – это многоуровневая форма организации объектов со строгой соотнесённостью объектов нижнего уровня определённому объекту верхнего уровня. Т. е. можно сказать, что иерархическая структура напоминает собой пирамиду, в которой объекты более низкого уровня подчиняются объектам более высокого уровня.
Из этого можно сделать вывод, что в иерархической структуре существуют отношения между её объектами (элементами).
Ещё иерархическую структуру называют древовидной. К примерам можно отнести содержание учебника.
А сейчас рассмотрим иерархическую структуру более подробно на примере.
Давайте построим иерархическую структуру школы.
Во главе всегда находится директор школы. Далее будут идти завуч старших классов, завуч младших классов, заведующий хозяйственной деятельностью. После завучей идут учителя, которые, соответственно, делятся на преподавателей младших и старших классов. Не будем расписывать всех учителей, а возьмём по три учителя каждых классов. Заведующему по хозяйственной деятельности будет подчиняться весь технический персонал. Его мы расписывать не будем. Далее у каждого учителя есть свой класс, в котором он является классным руководителем, а в каждом классе – ученики. В свою очередь, учителя старших классов ведут уроки и в других классах. Давайте отобразим несколько таких классов в нашей структуре. Если же всю эту структуру расписывать более подробно, то нам понадобится очень много места, так как объектов в этой системе очень большое количество.
Итак, во главе любой иерархической структуры всегда находится один элемент (объект). В нашем случае – это директор школы. Он является корнем вершины и находится на верхнем (первом) уровне.
Далее идёт второй уровень, на котором находятся заместители.
На третьем уровне находятся учителя и технический персонал, на четвёртом – классы и на пятом – ученики.
Как говорилось ранее, между всеми объектами существуют связи. Каждый объект более высокого уровня может включать в себя несколько объектов более низкого уровня. Давайте снова обратимся к нашему примеру. Так, завуч старшей школы включает в себя всех учителей, которые ведут уроки в старших классах. А заведующий хозяйственной деятельностью управляет всем техническим персоналом школы. Такие объекты находятся в отношении предка (объект более высокого уровня) к потомку (объект более низкого уровня). То есть завуч старшей школы и заведующий хозяйственной деятельностью являются предками, а учителя и технический персонал – потомками.
Также мы можем видеть, что у объекта-предка может быть несколько потомков. Но в то же время у объекта-потомка может быть только один предок. Объекты, которые находятся на одном уровне и у которых один общий предок, называются близнецами.
Рассмотрим ещё один пример. Построить иерархическую структуру, исходя из следующего условия: на кафедре иностранных языков работают три преподавателя. Иванова Инна Сергеевна преподаёт английский язык, Кулибина Анна Васильевна преподаёт немецкий язык, а Рудков Игорь Сергеевич преподаёт французский язык.
Корневой вершиной в этой структуре будет являться кафедра. Изобразим её в виде круга. Она включает в себя трёх преподавателей. Также изобразим их схематично, а от кафедры к каждому преподавателю проведём стрелки.
Далее у каждого преподавателя есть свои предметы, которые он ведёт. Также изобразим их схематично и проведём стрелки.
Таким образом мы получили графическое отображение иерархической структуры кафедры.
Корневой вершиной является кафедра.
Учителя являются потомками по отношению к кафедре и предками по отношению к предметам, которые они преподают. Также они между собой являются близнецами, так как находятся на одном уровне структуры и имеют одного предка – кафедру.
У нас получилось несколько определений.
Корень – это единственный объект, который стоит на вершине иерархической системы и является её первым уровнем.
Предок – это объект, который стоит более близко к корню системы и у него может быть несколько потомков.
Потомок – это объект, который стоит на более низком уровне по отношению к предку и у него может быть только один предок.
Близнецы – это объекты, которые имеют одного предка и находятся на одном уровне.
А сейчас рассмотрим ещё несколько примеров.
Начнём с иерархической базы данных папки Windows.
Иерархической базой данных является каталог папок Windows. Перед вами рисунок системного диска. Для того, чтобы увидеть древовидную структуру в проводнике в Windows 7, необходимо выбрать кнопку «Упорядочить», далее из появившегося списка – «Представления», а затем «Область переходов». Это в том случае, если данная область не отображается.
А вот, например, в Windows 10 необходимо в проводнике, во вкладке «Вид», выбрать «Область навигации» и из списка снова «Область навигации».
На рисунке представлен проводник операционной системы Windows 10.
Итак, корневой является папка «Этот компьютер».
Далее, на втором уровне на представленном рисунке находится локальный диск С, который включает в себя несколько папок третьего уровня.
В нашем случае выбрана папка «Program Files». Она в себя включает несколько папок-потомков.
Исходя из этого можно сказать, что корнем является – «Этот компьютер». Далее и предком, и потомком является локальный диск С. Папка «Program Files» также является и потомком (по отношению к локальному диску С), и предком (по отношению к остальным папкам, которые она в себя включает). Файл «Rar.txt» является потомком папки «WinRAR». В свою очередь, мы можем видеть, что у файла «Rar.txt» нет своих потомков. Также, например, файлы «Rar.txt» и «Rar.exe» являются близнецами, так как находятся на одном уровне и у них один общий предок – папка «WinRAR».
Ещё одним примером иерархической базы данных является файловая система Linux.
Мы ранее её рассматривали. В ней существует одна корневая папка, все остальные папки являются потомками. В корневой папке содержатся все системные файлы. А вот, например, каталоги логических томов и запоминающих устройств содержатся в составе других каталогов. Директории томов жёсткого диска содержатся в папке «mnt». Другие запоминающие устройства находятся в папке «media». В свою очередь, папки «mnt» и «media» содержатся в одном системном корневом каталоге. Таким образом, папки «mnt» и «media» являются и потомками (по отношению к основному корневому каталогу), и предками (по отношению к каталогам логических томов и запоминающих устройств). Помимо этого, эти две папки являются близнецами, так как они находятся на одном уровне и имеют одного предка.
А сейчас давайте рассмотрим такую иерархическую базу данных, как «Системный реестр Windows».
В этой иерархической базе данных хранится вся информация, которая нужна для нормального функционирования компьютерной системы. То есть в этой базе данных содержится информация о настройках компьютера, установленных драйверах, настройках графического интерфейса, сведения о программах, которые установлены на компьютере, и многое другое.
Вся эта информация автоматически обновляется при установке нового оборудования, удалении или установке программ и так далее.
Давайте рассмотрим рисунок.
Корневым объектом является сам компьютер. Папка «Adobe» является потомком по отношению к папке «SOFTWARE» и предком для всех остальных папок, которые она в себя включает. Папки «7-Zip» и «Adobe» являются близнецами, так как они находятся на одном уровне и у них один предок – папка «SOFTWARE». Файл «UserID» является потомком папки «IAC». В свою очередь, мы можем видеть, что у файла «UserID» нет своих потомков.
В операционной же системе Linux как такового реестра нет. Вместо этого в ней существует папка «etc».
А сейчас мы с вами рассмотрим иерархическую базу данных «Доменная система имён». Эта система получила название DNS.
DNS – это распределённая база данных, которая поддерживает иерархическую систему имён для идентификации узлов сети Интернет.
Эта служба предназначена для автоматического поиска IP-адреса по известному символьному имени узла. То есть в этой базе данных содержится информация о всех компьютерах, подключённых к сети Интернет.
Корневой вершиной в этой системе является табличная база данных, которая содержит перечень доменов верхнего уровня.
Сам же корень управляется центром Internet Network Information Center. Домены верхнего уровня назначаются для каждой страны, а также на организационной основе. Для обозначения стран используются трёхбуквенные и двухбуквенные аббревиатуры.
Так, например, для русскоязычных сайтов доменом верхнего уровня является «.ru», для Казахстана – «.kz» и т. д. Для различных типов организаций также есть свои аббревиатуры.
На втором уровне находятся также табличные базы данных, но они уже в себя включают перечень доменов второго уровня для каждого домена первого уровня.
На третьем уровне содержатся табличные базы данных и таблицы. Табличные базы данных содержат перечень доменов третьего уровня для каждого домена второго уровня. Таблицы, в свою очередь, содержат IP-адреса компьютеров, которые находятся в домене второго уровня.
А теперь представьте, какой большой будет база данных, которая должна включать в себя информацию о всех компьютерах, подключенных к Интернету. Как вы думаете, много ли места она будет занимать?
Такая база данных огромна по своим размерам и соответственно она не будет умещаться в памяти одного компьютера, а если бы и можно было загрузить такую базу данных в один компьютер, то работа в Интернете была бы очень медленной. Представьте себе количество запросов, которые поступают от пользователей всего мира в течение, например, 1 минуты. Их количество огромно. А теперь представьте, что все эти запросы должен принять и обработать один компьютер. Это просто невозможно, так как приведёт не только к медленной работе компьютера, но также и к зависанию, если не к поломке. Таким образом, размещение базы данных доменной системы имён на одном компьютере неэффективно. Но решение этой проблемы было найдено. Вся база данных была разделена на части и размещена на различных DNS-серверах, которые связаны между собой. Такая иерархическая база данных является распределённой базой данных.
А сейчас давайте рассмотрим, как происходит поиск информации в такой огромной иерархической распределённой базе данных.
Например, вам нужно зайти на свою почту в Яндексе. Для этого вы вводите в адресную строку запрос.
На этом сервере, в таблице первого уровня, произойдёт поиск интересующего нас домена «ru», после чего запрос будет перенаправлен на DNS-сервер второго уровня, который содержит перечень доменов второго уровня, зарегистрированных в домене «ru».
На втором уровне будет происходить поиск среди доменов второго уровня. После того, как был найден интересующий нас домен «yandex», произойдёт перенаправление на DNS-сервер третьего уровня, на котором находится перечень доменов третьего уровня, зарегистрированных в домене «yandex».
В таблице третьего уровня будет найден домен «mail», и запрос будет переадресован на DNS-сервер четвёртого уровня.
В таблице четвёртого уровня будет найдена запись, которая соответствует доменному имени, содержащемуся в запросе. После этого поиск в самой базе данных «Доменная система имён» будет завершён и начнётся поиск компьютера в сети по его IP-адресу.
Пришла пора подвести итоги урока.
Сегодня мы с вами узнали, что такое иерархическая структура и построили такую структуру на примере. Более подробно познакомились с элементами иерархической базы данных: корнем, предком, потомком, близнецами.
Рассмотрели несколько иерархических баз данных на примере Windows и Linux, а также реестра Windows.
Узнали, как составлена и работает иерархическая база данных «Доменная система имён».