UH COSC 3480 - File Organizations and Indexing (11 pages)

Previewing pages 1, 2, 3, 4 of 11 page document View the full content.
View Full Document

File Organizations and Indexing



Previewing pages 1, 2, 3, 4 of actual document.

View the full content.
View Full Document
View Full Document

File Organizations and Indexing

45 views

Other


Pages:
11
School:
University of Houston
Course:
Cosc 3480 - Design of File Database System

Unformatted text preview:

File Organizations and Indexing Chapter 8 How index learning turns no student pale Yet holds the eel of science by the tail Alexander Pope 1688 1744 atabase Management Systems R Ramakrishnan and J Gehrke Alternative File Organizations Many alternatives exist each ideal for some situation and not so good in others Heap files Suitable when typical access is a file scan retrieving all records Sorted Files Best if records must be retrieved in some order or only a range of records is needed Hashed Files Good for equality selections File is a collection of buckets Bucket primary page plus zero or more overflow pages Hashing function h h r bucket in which record r belongs h looks at only some of the fields of r called the search fields atabase Management Systems R Ramakrishnan and J Gehrke Cost Model for Our Analysis We ignore CPU costs for simplicity B The number of data pages R Number of records per page D Average time to read or write disk page Measuring number of page I O s ignores gains of pre fetching blocks of pages thus even I O cost is only approximated Average case analysis based on several simplistic assumptions Good enough to show the overall trends atabase Management Systems R Ramakrishnan and J Gehrke Assumptions in Our Analysis Single record insert and delete Heap Files Equality selection on key exactly one match Insert always at end of file Sorted Files Files compacted after deletions Selections on sort field s Hashed Files No overflow buckets 80 page occupancy atabase Management Systems R Ramakrishnan and J Gehrke Cost of Operations Sorted File BD Hashed File 1 25 BD Equality Search 0 5 BD D log2B D Range Search BD Insert 2D D log2B of 1 25 BD pages with matches Search BD 2D Delete Search D Search BD Scan all recs Heap File BD 2D Several assumptions underlie these rough estimates atabase Management Systems R Ramakrishnan and J Gehrke Indexes An index on a file speeds up selections on the search key fields for the index Any subset of the fields of a



View Full Document

Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...
Login

Join to view File Organizations and Indexing and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view File Organizations and Indexing and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?