Page reference patterns

1. Sequential References : Pages are referenced one after another.
   1. Straight Sequential
      1. Mostly the scan is done once w.o repetition.
      2. A single page frame is sufficient for the buffer space.
   2. Clustered Sequential
      1. A scan may back up a short distance & then start fwd again.
      2. Records in a cluster should be kept in the memory together.
   3. Looping Sequential
      1. A sequential reference may be repeated several times.
      2. Best Case : Entire file placed in memory.
      3. Best Algorithm : MRU replacement strategy.
2. Random References
   1. Independent Random
      1. A series of independent accesses.
      2. Example : An index scan through a secondary index.
   2. Clustered Random
      1. Locality of reference exists.
      2. If possible, each page having a record in a cluster is in memory.
3. Hierarchical References : Sequence of accesses that form a traversal path from the root down to the leaves of an index.
   1. Straight Hierarchical
      1. Index traversed only once.
      2. One buffer page sufficient.
      3. Tree traversal can be followed by a sequential scan through leaves.
   2. Hierarchical with Straight Sequential : If scan on the leaves is Straight Sequential
   3. Hierarchical with Clustered Sequential : If scan on the leaves is Clustered Sequential
   4. Looping Hierarchical : Repeated references to a heirarchical structure. The access probability of an index page at level i, (assuming root is at level 0) is inversely proportional to the ith power of the fan-out factor of an index page.