ntents 7. 7.1 Fixed-Length records 7.7.2 Variable-Length Records 7. 8 Points to review 8 FILE ORGANIZATIONS AND INDEXES 230 8. 1 Cost model 8.2 Comparison of Three File Organizations 232 8.2.1 Heap Files Sorted files Hashed files Choosing a File Organization 8. 3 Overview of Indexes 8. 3.1 Alternatives for Data Entries in an Index 4 Properties of Indexes 8. 4.1 Clustered versus Unclustered Indexe 8.4.2 Dense versus Sparse Indexes 994 8.4.3 Primary and Secondary Indexes 242 8.4.4 Indexes Using Composite Search Keys 8.5 Index Specification in SQL-g 8. 6 Points to review 9 TREE-STRUCTURED INDEXING 247 9.1 Indexed Sequential Access Method(ISAM) 248 9.2 B+ Trees: A Dynamic Index Structure 9.3 Format of a Node 9.5 Insert 9.6 Delete s 9.7 Duplicates 9.8 B+ Trees in Practice 9.8.1 Key Compression 9.8.2 Bulk-Loading a B+Tree The Order Concept he Effect of Inserts and Deletes on rids 9.9 Points to Review 10 HASH-BASED INDEXING 10.1 Static Hashing 23 .0.1.1 Notation and Conventions 10.2 Extendible Hashing 10.4 Extendible Hashing versus Linear Hashing 10.5 Points to reviewContents xi 7.7.1 Fixed-Length Records 222 7.7.2 Variable-Length Records 222 7.8 Points to Review 224 8 FILE ORGANIZATIONS AND INDEXES 230 8.1 Cost Model 231 8.2 Comparison of Three File Organizations 232 8.2.1 Heap Files 232 8.2.2 Sorted Files 233 8.2.3 Hashed Files 235 8.2.4 Choosing a File Organization 236 8.3 Overview of Indexes 237 8.3.1 Alternatives for Data Entries in an Index 238 8.4 Properties of Indexes 239 8.4.1 Clustered versus Unclustered Indexes 239 8.4.2 Dense versus Sparse Indexes 241 8.4.3 Primary and Secondary Indexes 242 8.4.4 Indexes Using Composite Search Keys 243 8.5 Index Specification in SQL-92 244 8.6 Points to Review 244 9 TREE-STRUCTURED INDEXING 247 9.1 Indexed Sequential Access Method (ISAM) 248 9.2 B+ Trees: A Dynamic Index Structure 253 9.3 Format of a Node 254 9.4 Search 255 9.5 Insert 257 9.6 Delete * 260 9.7 Duplicates * 265 9.8 B+ Trees in Practice * 266 9.8.1 Key Compression 266 9.8.2 Bulk-Loading a B+ Tree 268 9.8.3 The Order Concept 271 9.8.4 The Effect of Inserts and Deletes on Rids 272 9.9 Points to Review 272 10 HASH-BASED INDEXING 278 10.1 Static Hashing 278 10.1.1 Notation and Conventions 280 10.2 Extendible Hashing * 280 10.3 Linear Hashing * 286 10.4 Extendible Hashing versus Linear Hashing * 291 10.5 Points to Review 292