File Structures & External Data Structures (FSDS) PDF
Document Details
Tags
Summary
This document explains different methods for indexing in file structures and external data structures. It covers topics such as single and multi-key access, indexes in main memory and secondary memory, and different types of indexes like inverted indexes, bitmap indexes, and multi-level indexes. The document provides examples and diagrams.
Full Transcript
Chapter 3: Indexed Files Chapter Outline Basics : Definitions, Search keys, Index usage, … Single key access : Index in MM, Index in SM, Multi-level Index Multi-key access : Independent Indexes, Inverted Indexes, Bitmaps, … 23/10/2024...
Chapter 3: Indexed Files Chapter Outline Basics : Definitions, Search keys, Index usage, … Single key access : Index in MM, Index in SM, Multi-level Index Multi-key access : Independent Indexes, Inverted Indexes, Bitmaps, … 23/10/2024 File Structures & External Data Structures (FSDS) 86 Basics Searching for a record in a sequential file structure is usually expensive → sequential search → binary search in a (very) large file The attribute (or group of attributes) used to search for records is called “Search Key”: Examples : Weather measurement file Queries on search key ‘city’: → find the record(s) such as city = ‘DJELFA’ result : ‘DJELFA’ , ‘2015-06-23’ , 21 ‘DJELFA’ , ‘2013-10-04’ , 15 ’DJELFA’ , ‘2015-06-22’ , 20 ‘DJELFA’ , ‘2020-07-16’ , 29... → find the record(s) such as city < ‘MZZZ’ AND city > ‘ME’ result : ‘MSILA’ , ‘2011-04-23’ , 22 ‘MEDEA , ‘2019-02-04’ , 11 ‘MEFTAH , ‘2016-08-25’ , 32 ‘MILA’ , ‘2011-04-23’ , 14 ‘MOSTAGANEM’ , ‘2020-03-08’ , 19 23/10/2024... File Structures & External Data Structures (FSDS) 87 Index Table 23/10/2024 File Structures & External Data Structures (FSDS) 88 23/10/2024 File Structures & External Data Structures (FSDS) 89 Index usage 23/10/2024 File Structures & External Data Structures (FSDS) 90 Index usage 23/10/2024 File Structures & External Data Structures (FSDS) 91 Key values can be unique or multiple 23/10/2024 File Structures & External Data Structures (FSDS) 92 Different representations of multivalued index tables 23/10/2024 File Structures & External Data Structures (FSDS) 93 23/10/2024 File Structures & External Data Structures (FSDS) 94 23/10/2024 File Structures & External Data Structures (FSDS) 95 23/10/2024 File Structures & External Data Structures (FSDS) 96 Same example but keys with non-unique values 23/10/2024 File Structures & External Data Structures (FSDS) 97 23/10/2024 File Structures & External Data Structures (FSDS) 98 23/10/2024 File Structures & External Data Structures (FSDS) 99 23/10/2024 File Structures & External Data Structures (FSDS) 100 23/10/2024 File Structures & External Data Structures (FSDS) 101 23/10/2024 File Structures & External Data Structures (FSDS) 102 23/10/2024 File Structures & External Data Structures (FSDS) 103 23/10/2024 File Structures & External Data Structures (FSDS) 104 23/10/2024 File Structures & External Data Structures (FSDS) 105 23/10/2024 File Structures & External Data Structures (FSDS) 106 23/10/2024 File Structures & External Data Structures (FSDS) 107 23/10/2024 File Structures & External Data Structures (FSDS) 108 23/10/2024 File Structures & External Data Structures (FSDS) 109 23/10/2024 File Structures & External Data Structures (FSDS) 110 23/10/2024 File Structures & External Data Structures (FSDS) 111
