CISC437 Lecture Notes - Lecture 20: Analysis Of Algorithms, Database, Unique Key

• School: University of Delaware
• Department: Computer and Information Sciences
• Course: CISC437
• Professor: Carterette Benjamin

Document Summary

Database algorithm analysis model: goal is to minimize block reads, variables. B: number of blocks a file is stored in. C: time it takes to process 1 record. R: average # records in 1 block: total time to scan a file: d*b + c*(r*b, analyze in terms of o(b) 6 operations to analyze: full file scan (select with no key, search on key (select with a key, range search on key (select with range of keys, insert, search/update non key field, delete. 2 main ways to store a file: heap file: records stored in random order, sequential file: records stores in sorted order (usually stored by primary keys) A separate data structure that speeds up access to data: each index record has 3 pieces of data. Pointer(s) to block(s) where record is stored. Like tables, indexes are stored in files: special kind of able.