《数据库系统概念 Database System Concepts》原书教学资源（第七版，PPT课件讲稿，英文版）Chapter 13 Data Storage Structures

File Organization The database is stored as a collection of files.Each file is a sequence of records.A record is a sequence of fields. One approach Assume record size is fixed Each file has records of one particular type only Different files are used for different relations This case is easiest to implement;will consider variable length records later We assume that records are smaller than a disk block Database System Concepts-7th Edition 13.2 ©Silberscha乜，Korth and Sudarshan

Database System Concepts - 7 13.2 ©Silberschatz, Korth and Sudarshan th Edition File Organization ▪ The database is stored as a collection of files. Each file is a sequence of records. A record is a sequence of fields. ▪ One approach • Assume record size is fixed • Each file has records of one particular type only • Different files are used for different relations This case is easiest to implement; will consider variable length records later ▪ We assume that records are smaller than a disk block

Fixed-Length Records Simple approach: Store record i starting from byte n *(i-1),where n is the size of each record. Record access is simple but records may cross blocks Modification:do not allow records to cross block boundaries record 0 10101 Srinivasan Comp.Sci. 65000 record 1 12121 Wu Finance 90000 record 2 15151 Mozart Music 40000 record 3 22222 Einstein Physics 95000 record 4 32343 El Said History 60000 record 5 33456 Gold Physics 87000 record 6 45565 Katz Comp.Sci. 75000 record 7 58583 Califieri History 62000 record 8 76543 Singh Finance 80000 record 9 76766 Crick Biology 72000 record 10 83821 Brandt Comp.Sci. 92000 record 11 98345 Kim Elec.Eng. 80000 Database System Concepts-7th Edition 13.3 @Silberschatz,Korth and Sudarshan

Database System Concepts - 7 13.3 ©Silberschatz, Korth and Sudarshan th Edition Fixed-Length Records ▪ Simple approach: • Store record i starting from byte n  (i – 1), where n is the size of each record. • Record access is simple but records may cross blocks ▪ Modification: do not allow records to cross block boundaries

Fixed-Length Records Deletion of record i:alternatives: move recordsi+1,...,n to i,...,n-1 move recordn to i do not move records.but link all free records on a free list Record 3 deleted record 0 10101 Srinivasan Comp.Sci. 65000 record 1 12121 Wu Finance 90000 record 2 15151 Mozart Music 40000 record 4 32343 El Said History 60000 record 5 33456 Gold Physics 87000 record 6 45565 Katz Comp.Sci. 75000 record 7 58583 Califieri History 62000 record 8 76543 Singh Finance 80000 record 9 76766 Crick Biology 72000 record 10 83821 Brandt Comp.Sci. 92000 record 11 98345 Kim Elec.Eng. 80000 Database System Concepts-7th Edition 13.4 @Silberschatz,Korth and Sudarshan

Database System Concepts - 7 13.4 ©Silberschatz, Korth and Sudarshan th Edition Fixed-Length Records ▪ Deletion of record i: alternatives: • move records i + 1, . . ., n to i, . . . , n – 1 • move record n to i • do not move records, but link all free records on a free list Record 3 deleted

Fixed-Length Records Deletion of record i:alternatives: move records i+1,...,n to i,...,n-1 move record n to i do not move records,but link all free records on a free list Record 3 deleted and replaced by record 11 record 0 10101 Srinivasan Comp.Sci. 65000 record 1 12121 Wu Finance 90000 record 2 15151 Mozart Music 40000 record 11 98345 Kim Elec.Eng. 80000 record 4 32343 El Said History 60000 record 5 33456 Gold Physics 87000 record 6 45565 Katz Comp.Sci. 75000 record 7 58583 Califieri History 62000 record 8 76543 Singh Finance 80000 record 9 76766 Crick Biology 72000 record 10 83821 Brandt Comp.Sci. 92000 Database System Concepts-7th Edition 13.5 @Silberschatz,Korth and Sudarshan

Database System Concepts - 7 13.5 ©Silberschatz, Korth and Sudarshan th Edition Fixed-Length Records ▪ Deletion of record i: alternatives: • move records i + 1, . . ., n to i, . . . , n – 1 • move record n to i • do not move records, but link all free records on a free list Record 3 deleted and replaced by record 11

Fixed-Length Records Deletion of record i:alternatives: move records i+1,...,n to i,...,n-1 move recordn to i do not move records,but link all free records on a free list header record 0 10101 Srinivasan Comp.Sci. 65000 record 1 record 2 15151 Mozart Music 40000 record 3 22222 Einstein Physics 95000 record 4 record 5 33456 Gold Physics 87000 record 6 record 7 58583 Califieri History 62000 record 8 76543 Singh Finance 80000 record 9 76766 Crick Biology 72000 record 10 83821 Brandt Comp.Sci. 92000 record 11 98345 Kim Elec.Eng. 80000 Database System Concepts-7th Edition 13.6 @Silberschatz,Korth and Sudarshan

Database System Concepts - 7 13.6 ©Silberschatz, Korth and Sudarshan th Edition Fixed-Length Records ▪ Deletion of record i: alternatives: • move records i + 1, . . ., n to i, . . . , n – 1 • move record n to i • do not move records, but link all free records on a free list

Variable-Length Records Variable-length records arise in database systems in several ways: Storage of multiple record types in a file. Record types that allow variable lengths for one or more fields such as strings(varchar) Record types that allow repeating fields (used in some older data models). Attributes are stored in order Variable length attributes represented by fixed size (offset,length),with actual data stored after all fixed length attributes Null values represented by null-value bitmap Null bitmap (stored in 1 byte) 0000 21,5 26,10 36,10 65000 10101 Srinivasan Comp.Sci. Bytes 0 4 8 12 2021 26 36 45 Database System Concepts-7th Edition 13.7 @Silberschatz,Korth and Sudarshan

Database System Concepts - 7 13.7 ©Silberschatz, Korth and Sudarshan th Edition Variable-Length Records ▪ Variable-length records arise in database systems in several ways: • Storage of multiple record types in a file. • Record types that allow variable lengths for one or more fields such as strings (varchar) • Record types that allow repeating fields (used in some older data models). ▪ Attributes are stored in order ▪ Variable length attributes represented by fixed size (offset, length), with actual data stored after all fixed length attributes ▪ Null values represented by null-value bitmap

Variable-Length Records:Slotted Page Structure Block Header Records Size Entries Free Space Location End of Free Space Slotted page header contains: number of record entries end of free space in the block location and size of each record ■ Records can be moved around within a page to keep them contiguous with no empty space between them;entry in the header must be updated. Pointers should not point directly to record-instead they should point to the entry for the record in header. Database System Concepts-7th Edition 13.8 @Silberschatz,Korth and Sudarshan

Database System Concepts - 7 13.8 ©Silberschatz, Korth and Sudarshan th Edition Variable-Length Records: Slotted Page Structure ▪ Slotted page header contains: • number of record entries • end of free space in the block • location and size of each record ▪ Records can be moved around within a page to keep them contiguous with no empty space between them; entry in the header must be updated. ▪ Pointers should not point directly to record — instead they should point to the entry for the record in header

Storing Large Objects E.g.,blob/clob types Records must be smaller than pages Alternatives: Store as files in file systems Store as files managed by database Break into pieces and store in multiple tuples in separate relation ·PostgreSQL TOAST Database System Concepts-7th Edition 13.9 ©Silberscha乜，Korth and Sudarshan

Database System Concepts - 7 13.9 ©Silberschatz, Korth and Sudarshan th Edition Storing Large Objects ▪ E.g., blob/clob types ▪ Records must be smaller than pages ▪ Alternatives: • Store as files in file systems • Store as files managed by database • Break into pieces and store in multiple tuples in separate relation ▪ PostgreSQL TOAST

Organization of Records in Files Heap-record can be placed anywhere in the file where there is space ■ Sequential-store records in sequential order,based on the value of the search key of each record ■ In a multitable clustering file organization records of several different relations can be stored in the same file Motivation:store related records on the same block to minimize 1/O B+-tree file organization Ordered storage even with inserts/deletes More on this in Chapter 14 Hashing-a hash function computed on search key;the result specifies in which block of the file the record should be placed More on this in Chapter 14 Database System Concepts-7th Edition 13.10 ©Silberscha乜，Korth and Sudarshan

Database System Concepts - 7 13.10 ©Silberschatz, Korth and Sudarshan th Edition Organization of Records in Files ▪ Heap – record can be placed anywhere in the file where there is space ▪ Sequential – store records in sequential order, based on the value of the search key of each record ▪ In a multitable clustering file organization records of several different relations can be stored in the same file • Motivation: store related records on the same block to minimize I/O ▪ B+ -tree file organization • Ordered storage even with inserts/deletes • More on this in Chapter 14 ▪ Hashing – a hash function computed on search key; the result specifies in which block of the file the record should be placed • More on this in Chapter 14

Heap File Organization Records can be placed anywhere in the file where there is free space Records usually do not move once allocated Important to be able to efficiently find free space within file ■Free-space map Array with 1 entry per block.Each entry is a few bits to a byte,and records fraction of block that is free In example below,3 bits per block,value divided by 8 indicates fraction of block that is free 4214736512011056 Can have second-level free-space map In example below,each entry stores maximum from 4 entries of first- level free-space map 4726 Free space map written to disk periodically,OK to have wrong (old)values for some entries(will be detected and fixed) Database System Concepts-7th Edition 13.11 @Silberschatz,Korth and Sudarshan

Database System Concepts - 7 13.11 ©Silberschatz, Korth and Sudarshan th Edition Heap File Organization ▪ Records can be placed anywhere in the file where there is free space ▪ Records usually do not move once allocated ▪ Important to be able to efficiently find free space within file ▪ Free-space map • Array with 1 entry per block. Each entry is a few bits to a byte, and records fraction of block that is free • In example below, 3 bits per block, value divided by 8 indicates fraction of block that is free • Can have second-level free-space map • In example below, each entry stores maximum from 4 entries of first￾level free-space map ▪ Free space map written to disk periodically, OK to have wrong (old) values for some entries (will be detected and fixed)