The course presents the fundamental file structures as well as the associated algorithms.
Designing efficient algorithms for handling large volumes of data on external memory requires a deep understanding of the issues related to input / output operations. This course addresses this problem by presenting the different structures and organization of data (in secondary and primary memory) as well as the study of the associated algorithms including their complexity and efficiency.
This is what is taught in the SFSD module at ESI in Algiers.
0- Course presentation (slides)
1- General concepts - (slides)
Notion of files, buffered I / O,
Files at application level, C Streams,
Model for file structures at the physical level, Complexity and cost of file operations,
Header Block and File Characteristics.
2- Simple file structures - (slides)
Sequential Access Structures, Contiguous Blocks, Chained Blocks,
Sorted files, External Binary Search, Periodic Reorganizations, File Merging,
Variable-Size Records, handling of Interblock overlaps.
3- Indexed files - (slides)
Index in main memory, Primary index, Secondary index, loading operation, Index backup,
Index in secondary storage, Inverted lists, Multi-key access, Multi-level index, Bitmap index ...
4- Trees in secondary storage
M-ary search trees in secondary memory (slides)
B Trees (slides)
Variants of B-trees: B+, B*, Prefixed B+ (slides)
(see examples of C programs : B-tree file structure )
5- Hashing in secondary storage - (slides)
Static hashing methods
Dynamic hashing methods (Linear Hashing).
6- High level operations on files
Sorting files (slides)
- Multi-Files Merging Algorithm , External Sort Algorithm
Join Algorithms (slides)
- Nested-Loops Join algorithm , Sort-Merge Join algorithm , Hash Join algorithm
Parallelism in high level operations (slides)
(see examples of C programs : External sort, Multi-Files merging and Parallel sorting for clusters)
Here is the full handout (document in PDF) covering all the chapters of the course.
يتطلب تصميم خوارزميات فعالة لمعالجة كميات كبيرة من البيانات الموجودة على الذاكرة الخارجية فهماً شاملاً للقضايا المرتبطة بعمليات الإدخال / الإخراج.
يتناول هذا المقرر الدراسي هذه القضية من خلال عرض الهياكل المختلفة وتنظيم البيانات (في الذاكرة الثانوية والذاكرة الأولية) وكذلك دراسة الخوارزميات المرتبطة بما في ذلك تعقيدها وكفاءتها.
الكلمات الرئيسية
الملف ، الإدخال / الإخراج المادي ، هياكل الملفات ، المخزن المؤقت ، كتلة الإدخال / الإخراج، ذاكرة التخزين المؤقت ، الذاكرة الثانوية: انظر الفصل 1
ملف تسلسلي ، ملف مرتب ، تنظيم فعلي في شكل قائمة ، تنظيم متجاور ، سجلات متغيرة الحجم ، تحميل أولي ، إعادة تنظيم دوري: انظر الفصل 2
فهرس أولي ، فهرس ثانوي ، فهرس متعدد المستويات ، بحث متعدد المفاتيح ، فهرس نقطي: انظر الفصل 3
شجرة بحث متعددة الاتجاهات, الأشجار المتوازنة: انظر الفصل 4
التجزئة ، التجزئة الخطية: انظر الفصل 5
دمج الملفات ، تجزئة الملف ، خوارزمية الفرز الخارجي ، خوارزمية الدمج المتعدد ، الدمج المتوازي ، الفرز المتوازي ، خوارزميات الانضمام (حلقات متداخلة ، فرز ودمج ، تجزئة). انظر الفصل 6
La conception d'algorithmes efficaces pour traiter de grands volumes de données sur la mémoire externe nécessite une compréhension approfondie des problèmes liés aux opérations d'entrée / sortie.
Ce cours aborde cette problématique en présentant les différentes structures et organisation des données (en mémoire secondaire et primaire) ainsi que l'étude des algorithmes associés incluant leur complexité et leur efficacité.
Mot-clés
fichier, E/S physique, structure de fichier, buffer, bloc, zone tampon, mémoire secondaire : voir chapitre 1
fichier séquentiel, fichier ordonné, liste de blocs, blocs contigus, enregistrement à taille variable, chargement initial, réorganisation périodique : voir chapitre 2
index primaire, index secondaire, index multi-niveaux, accès multi-clés, index bitmap : voir chapitre 3
arbre de recherche m-aire, B-arbre : voir chapitre 4
hachage, hachage linéaire : voir chapitre 5
fusion de fichiers, fragmentation d’un fichier, algorithme de tri externe, algorithme de multi-fusion, fusion parallèle, tri parallèle, algorithme de jointure par boucles imbriquées, algorithme de jointure par tri-fusion, algorithme de jointure par hachage : voir chapitre 6