ку, що відзначає перший оброблювану запис, називається покажчиком списку. Адреса зв'язку, що відзначає перше вільне позицію пам'яті, називається покажчиком вільної пам'яті. Адреса зв'язку останнього запису (або останнього запису вільної пам'яті) у списку називається кінцем списку, і відзначається нульовим значенням.
деревовидних організацією даних (деревом) називається безліч записів, розташованих за рівнями наступним чином:
на 1-му рівні розташована тільки один запис (корінь дерева)
до будь-якого запису i-го рівня веде адреса зв'язку від одного запису рівня i - 1.
У даному визначенні поняття дерево і рівень вводяться одночасно. Якщо записи отримають номери рівнів, що відповідають визначенню, то вони отримають і деревоподібну організацію. Кількість рівнів у дереві називається рангом. Записи дерева, які адресуються від загальної запису (i - 1) -го рівня, утворюють групу. Максимальне число елементів в групі називається порядком дерева. Дерева зазвичай формуються двонаправленими, адреса зв'язку від запису рівня i + 1 до запису i-го рівня називається зворотним.
При розміщенні дерева в пам'яті ЕОМ кожен запис може займати довільне місце. Назвемо ланкою зв'язку набір адрес зв'язку, що належать одній запису. Якщо порядок дерева дорівнює р, то ланка зв'язку складається з р + 1 адрес (одна адреса зворотний, що визначає зв'язок із записом безпосередньо більш високого рівня). Корінь дерева адресується із спеціального покажчика дерева. Незайняті адреси зв'язку містять ознака кінця списку. Послідовна, ланцюгова бінарна деревоподібна організації даних призначені для вирішення загальної задачі - обробки записів з одним ключовим атрибутом. Оскільки вони взаємозамінні, має сенс завдання вибору найкращої організації даних. За критерієм часу формування даних ланцюгової каталог і бінарне дерево мають певні переваги перед послідовним масивом, незважаючи на те, що процеси формування описуються однаковими формулами. За часом пошуку послідовний масив і бінарне дерево переважніше ланцюгового каталогу. Мінімальний час коригування характерно для бінарного дерева, а мінімальний обсяг додаткової пам'яті - для послідовного масиву.
Таким чином, абсолютно бездоганного методу організації даних не існує. Однак, мінімальний час зазвичай вважається більш важливим критерієм, ніж мінімальна додаткова пам'ять, і тоді кращим методом організації даних в оперативній пам'яті ЕОМ необхідно визнати впорядковане бінарне дерево.
2. Організація даних у зовнішній пам'яті ЕОМ
В якості зовнішньої пам'яті ЕОМ використовуються в основному пристрої електромагнітної запису сигналів, для яких характерне приблизна рівність витрат часу на читання і запис інформації, - магнітні диски. На відміну від оперативної пам'яті ЕОМ для них перед безпосередньо читанням/записом потрібно підведення необхідної ділянки магнітного носія до механізму читання/запису (у реальних запам'ятовуючих пристроях можуть рухатися і носій даних, і механізм читання/запису) .Тому час доступу до даних на зовнішньому запам'ятовуючому пристрої залежить від місця розташування даних на диску або стрічці, що істотно відрізняє їх від оперативної пам'яті і визначає специфіку організації даних у зовнішній пам'яті ЕОМ.
Дані на зовнішньому запам'ятовуючому пристрої зберігаються у вигляді файлів.
Файл являє собою безліч логічно пов'язаних записів.
Запис зазвичай відповідає одному значенню деякої складовою одиниці інформації. Кожен файл має унікальне ім'я файлу. У найпростішому випадку файл являє послідовний масив записів на зовнішньому запам'ятовуючому пристрої. Організація зовнішньої пам'яті персональних ЕОМ має ряд відмінностей від принципів, що використовуються в міні-ЕОМ і середніх ЕОМ. Вся зовнішня пам'ять розділена на фізичні блоки (сектори), що мають фіксований розмір (зазвичай 512 байт), який не залежить від бажання проектувальника системи.
Обмін з оперативною пам'яттю відбувається тільки цілими секторами.
Коли проводиться тільки послідовна обробка файлу, оптимальний (з погляду мінімального часу доступу) розмір блоку повинен бути найбільш великим з можливих; коли відбувається тільки вибірка одиночних записів, оптимальними є блоки розміром в одну запис.
Існує ряд стандартних методів організації файлів на магнітному диску і відповідно методів доступу до цих файлів. Серед них - послідовна, індексного-послідовна, індексного-довільна і пряма організація файлів. У всіх випадках необхідно виділення в записах файлу одного ключового атрибута.
При послідовної організації файлу на магнітному диску можливий доступ від щойно обробленої записи до подальшого запису (у напрямк...
