Data Storage and Structures
An Introduction
|
Prof. David Bernstein
James Madison University
|
|
Computer Science Department |
bernstdh@jmu.edu |
|
Motivation
- Almost all applications require a large number of entities
- We may or may not know a lot about the number and nature of
these elements before the application is executed
- The organization/storage of the entities will depend on what
we do and do not know
An Analogous Situation
- Why Use an Analogy?
- The data storage problem is fairly conceptual
- It often helps to consider a physical analogue
- The Physical Analogue:
- A warehouse containing outgoing orders
An Analogous Situation (cont.)
- The Setting:
- Each order can consists of multiple items
- Items can be different sizes
- An Example with Two Customers:
An Analogous Situation (cont.)
- The Setting (cont.):
- The warehouse is filled with a number of different bins
- The dividers between the bins are removable
- An Illustration:
An Analogous Situation (cont.)
Storing an Order for A
An Analogous Situation (cont.)
Storing Orders for A and B
An Order for C
An Analogous Situation (cont.)
- A Problem:
- This order cannot be stored contiguously without moving
the other orders around
- It is fairly expensive to move items
- A Solution: Break the Order into Pieces
- They can place an arrow with a number on it
in any bin
- The arrow is used to indicate that this order
continues in another bin
An Analogous Situation (cont.)
- Continuing with the Example:
- Place two "small" items in bins 3 and 4
- Place an "arrow" in bin 5 indicating the order
continues in bin 11
- Place two "large" items in bins 11-14
- An Illustration:
An Analogous Situation (cont.)
- A Problem:
- As the warehouse gets full, it becomes increasingly
difficult to keep track of orders
- A Solution: A Manifest
- When an order is placed in contiguous bins the
manifest shows the first bin and the number of
bins in the order
- When the order is broken into pieces, the manifest
contains the location of the bin containing the first
part of the order
An Analogous Situation (cont.)
An Example of a Manifest
An Analogous Situation (cont.)
- The number of items is known but the specifics of each item
(e.g., the size) are not
- Leaving enough space in the manifest for all of
the different pieces of the order but don't fill
in the location and bin requirements
- The specifics of each item (e.g., the size) are known, but the
number of items is not
- Guess at the number of items and leave
enough bins to handle that number
- If more bins are required, the "arrows" can be used
to locate the remainder of the order
- Nothing is known about the order
- The order will probably need to be stored in a large
number of pieces (using the "arrows" to keep track of the pieces)
Organization/Storage of Data
- Data Structures:
- Used to organize the storage and retrieval of
data values
- A realization in computer memory of a set of values
- Contents of Data Structures:
-
Homogeneous (i.e., identical) elements
-
Heterogeneous (i.e., different) elements
Using the Analogy
- The Important Observations:
- Random access memory (RAM) and "permanent"
memory stores (e.g., disks) have many of the
properties of the warehouse
- Each element (i.e.,
int
, float
)
to be stored has a size (in bytes)
- The "manifest" from the warehouse example is analogous
to named variables
- Memory as a Sequence of Bytes:
Structures that use Contiguous Locations
- When We Know...
- The size of each element
- The number of elements
- An Illustration:
Structures that use Non-Contiguous Locations
- When We Don't Know...
- Either the number of elements
- Or the size of the elements
- An Illustration:
- Suppose use the first four bytes to store the
size/compositionn of the element and the last
four bytes to store the address of the next element
-
-