File Organizations and Indexes in Software

Maker Data Matrix 2d barcode in Software File Organizations and Indexes

records that follow the deleted record must be moved up to compact the free space2 The cost is the same as for an insert, that is, search cost plus B(D + RC) Given the rid of the record to delete, we can fetch the page containing the record directly If records to be deleted are speci ed by an equality or range condition, the cost of deletion depends on the number of qualifying records If the condition is speci ed on the sort eld, qualifying records are guaranteed to be contiguous due to the sorting, and the rst qualifying record can be located using binary search

A simple hashed le organization enables us to locate records with a given search key value quickly, for example, Find the Students record for Joe, if the le is hashed on the name eld The pages in a hashed le are grouped into buckets Given a bucket number, the hashed le structure allows us to nd the primary page for that bucket The bucket to which a record belongs can be determined by applying a special function called a hash function, to the search eld(s) On inserts, a record is inserted into the appropriate bucket, with additional over ow pages allocated if the primary page for the bucket becomes full The over ow pages for each bucket are maintained in a linked list To search for a record with a given search key value, we simply apply the hash function to identify the bucket to which such records belong and look at all pages in that bucket This organization is called a static hashed le, and its main drawback is that long chains of over ow pages can develop This can a ect performance because all pages in a bucket have to be searched Dynamic hash structures that address this problem are known, and we discuss them in 10; for the analysis in this chapter, we will simply assume that there are no over ow pages Scan: In a hashed le, pages are kept at about 80 percent occupancy (to leave some space for future insertions and minimize over ow pages as the le expands) This is achieved by adding a new page to a bucket when each existing page is 80 percent full, when records are initially organized into a hashed le structure Thus, the number of pages, and the cost of scanning all the data pages, is about 125 times the cost of scanning an unordered le, that is, 125B(D + RC) Search with equality selection: This operation is supported very e ciently if the selection is on the search key for the hashed le (Otherwise, the entire le must

a heap le, there is no inexpensive way to manage free space, so we account for the cost of compacting a le when a record is deleted

8

be scanned) The cost of identifying the page that contains qualifying records is H; assuming that this bucket consists of just one page (ie, no over ow pages), retrieving it costs D The cost is H + D + 05RC if we assume that we nd the record after scanning half the records on the page This is even lower than the cost for sorted les If there are several qualifying records, or none, we still have to retrieve just one page, but we must scan the entire page Note that the hash function associated with a hashed le maps a record to a bucket based on the values in all the search key elds; if the value for any one of these elds is not speci ed, we cannot tell which bucket the record belongs to Thus, if the selection is not an equality condition on all the search key elds, we have to scan the entire le Search with range selection: The hash structure o ers no help; even if the range selection is on the search key, the entire le must be scanned The cost is 125B(D + RC) Insert: The appropriate page must be located, modi ed, and then written back The cost is the cost of search plus C + D Delete: We must search for the record, remove it from the page, and write the modi ed page back The cost is again the cost of search plus C + D (for writing the modi ed page) If records to be deleted are speci ed using an equality condition on the search key, all qualifying records are guaranteed to be in the same bucket, which can be identi ed by applying the hash function