Reading Note From Textbook

The unit for data transfer between disk and main memory is a block; if a single item on a block is needed, the entire block is transferred. Reading or writing a disk block is called an I/O (for input/output) operation.

INDEXED SEQUENTIAL ACCESS METHOD:

Data on the leafs, static except for the overflow pages Each tree node is a disk page, and all the data resides in the leaf pages. For insertion if there is no space, create the overflow pages. But the downside is that these chains can significantly affect the time to retrieve a record because the overflow chain has to be searched as well when the search gets to this leaf.

When is it good?: Since we only edit the leaf pages, index-level pages are never modified, we can safely omit the locking step, which outperforms the B+ Tree. If the data distribution and size are relatively static, which means overflow chains are rare, ISAM might be preferable to B+ trees due to this advantage.

B+ Tree:

A balanced tree where internal node direct the search and leaf nodes contain data entries. Link the data entries using page pointers, organized to a double-linkedList which we could traverse in both directions

• A minimum occupancy of 50 percent is guaranteed for each node except the root
• A file of records

Until 10.6

Algorithms: