Base organizations

Question 1

Serial media

Answer 1

Physical storage device where records are stored one after another in sequence.

Question 2

Serial organization

Answer 2

Storing records without any specific ordering or location criteria.

Question 3

Physical deletion

Answer 3

The record is removed and subsequent records are physically shifted to fill the gap.

Question 4

Logical deletion

Answer 4

The record is marked as deleted, leaving a gap in its place.

Question 5

Update on constant-sized record

Answer 5

The content of the record is modified in-place without changing its size.

Question 6

Update on non-consecutive record

Answer 6

If a sufficiently large gap exists elsewhere, the record is updated in that location.

Question 7

Retrieval with identifying selective key

Answer 7

The system reads records sequentially until a matching record is found.

Question 8

Distributed free space (DFS)

Answer 8

Reserved percentage of space in each bucket dedicated to updates, reducing the need to move records.

Question 9

Gaps list

Answer 9

In-memory structure that tracks locations in the file with available space for insertions.

Question 10

Compacting

Answer 10

Maintenance process of physically reorganizing records to eliminate gaps and restore density.

Question 11

Overflow

Answer 11

Occurs when a record cannot be inserted in its sorted position due to lack of space.

Question 12

Degeneration

Answer 12

Gradual growth of unsorted areas in a sequential organization due to repeated unsorted insertions.

Question 13

Extended binary search

Answer 13

A binary search followed by scanning forward and backward to retrieve all matching records.

Question 14

Overflow management (consecutive organization)

Answer 14

Uses a dedicated unsorted area for handling overflowed records.

Question 15

Overflow management (non-consecutive organization)

Answer 15

Uses techniques like rotations, bucket interleaving, and cell partitions to manage overflow.

Question 16

Overflow management - rotations

Answer 16

Moves records from a full bucket into a neighboring bucket with available space.

Question 17

Overflow management - bucket interleaving

Answer 17

Reserves empty buckets during file creation for future overflow handling.

Question 18

Overflow management - cell partitions

Answer 18

Adds an empty bucket directly after an overflowed bucket and stores excess records there.

Question 19

Direct addressing organization

Answer 19

Each record is stored at a bucket whose address directly corresponds to the key value.

Question 20

Absolute direct addressing

Answer 20

The key itself is used directly as the bucket address.

Question 21

Relative addressing

Answer 21

A bijective function maps the key to a unique bucket address.

Question 22

Transformation function

Answer 22

A non-reversible function that converts a key into a bucket address for hashing.

Question 23

Synonymous keys

Answer 23

Different keys that result in the same bucket address under a specific hash function.

Question 24

Homonymous keys

Answer 24

Identical key values that always map to the same bucket.

Question 25

Addressing capability

Answer 25

The number of possible key values should be greater than or equal to the number of buckets to reduce collisions.

Question 26

Collision

Answer 26

When two different records are assigned to the same bucket address.

Question 27

Saturation

Answer 27

Overflow records are stored elsewhere within the same address space using an alternate strategy.

Question 28

Address space

Answer 28

The total number of possible bucket addresses available for storing records.

Question 29

Overflow area

Answer 29

A separate storage region used specifically for handling overflowed records.

Question 30

Open addressing

Answer 30

Overflow handling technique that searches for a new available bucket within the same address space.

Question 31

Progressive chained saturation

Answer 31

Overflow records are stored in another location with the original bucket pointing to them via a pointer.

Question 32

Chained overflow area

Answer 32

An overflow bucket is created in a separate area and linked to the original bucket.

Question 33

Independent overflow area

Answer 33

Overflow records are stored in a completely separate archive, with no pointer from the original bucket.

Question 34

Static hashing

Answer 34

Hashing method where records are placed in buckets using a fixed hash function and a fixed number of buckets.

Question 35

Rebound

Answer 35

A condition where an overflowed record cannot be inserted into its primary or subsequent buckets due to lack of space.

Question 36

Global addressing space

Answer 36

The total number of possible addresses that can be generated by the hash function.

Question 37

Extendable hashing

Answer 37

A dynamic hashing method where more bits of the hash are used as needed to expand the number of buckets.

Question 38

Virtual hashing

Answer 38

Uses a directory to track which buckets are actually in use, avoiding physical storage of empty buckets.

Question 39

Dynamic hashing

Answer 39

Hashing method where the directory structure grows like a tree to adapt to changes in data volume or distribution.

Question 40

Cluster

Answer 40

File organization method that physically stores related records together using a shared clustering key.

Question 41

Serial cluster

Answer 41

Cluster where records are grouped together but not sorted internally.

Question 42

Sorted cluster

Answer 42

Cluster where records are sorted by a sorting key that is part of the clustering key.

Question 43

Hashed cluster

Answer 43

Cluster where the clustering key is hashed to determine the storage location.

Question 44

Indexed cluster

Answer 44

Cluster that uses indexes to locate groups of related records based on the clustering key.

Question 45

Why use clusters

Answer 45

To reduce disk I/O by physically grouping related data, and to optimize grouped or joined queries.

Question 46

Cluster identity

Answer 46

A set of records stored together that share the same value for the clustering key.

Question 47

Disadvantages of automatic reordering

Answer 47

Requires a full file scan, may not align with business logic, and can poorly balance cost vs. performance.