What are the four types of data storage structures?

Recommended tutorial: windows operation and maintenance tutorial

##Storage Structures are divided into four categories: sequential storage, linked storage, index storage and hash storage.

Sequential structures and link structures are applicable to memory structures.

Index structure and hash structure are suitable for external storage and memory interaction structures.

1. Sequential storage

In the computer, a set of storage units with consecutive addresses are used to store the linear table in sequence. Each data element is called a sequential storage structure of a linear list.

Features:

1. Randomly access elements in the table.

　2. Insertion and deletion operations require moving elements.

2. Linked storage

Use a set of arbitrary storage units in the computer to store the data elements of the linear table (This group of storage units can be continuous or discontinuous). It does not require that logically adjacent elements are also physically adjacent. Therefore, it does not have the weaknesses of the sequential storage structure, but it also loses the advantage of random access of the sequential list.

Features:

1. The storage density is smaller than the sequential storage structure (each node is composed of data fields It consists of a pointer field and a pointer field, so if the same space is full, the order will be more than that of chained storage). 　2. Logically adjacent nodes do not have to be physically adjacent.
　3. Flexible insertion and deletion (no need to move the node, just change the pointer in the node).
　4. Chained storage is slower than sequential storage when searching for nodes.
　5. Each node is composed of data field and pointer field.

3. Index storage

In addition to creating storage node information, additional index tables are also created to identify The address of the node. The index table consists of several index entries.

Features:

The index storage structure uses the index number of the node to determine the node storage address. The advantage is that the retrieval speed is fast, but the disadvantage is that additional index tables are added, which takes up more storage space.

4. Hash storage

Hash storage, also known as hash storage, is an attempt to store data A search technology that establishes a certain correspondence between the storage location of an element and its key code.

The basic idea of ​​hash storage is: the key value of the node determines the storage address of the node. In addition to being used for lookup, hashing technology can also be used for storage.

Features:

Hashing is a development of array storage. Compared with arrays, hashing The data access speed is higher than that of the array, because the storage location of the data in the array can be found based on part of the stored data, and the data can be accessed quickly. The ideal hash access speed is very fast, unlike in the array In the traversal process, some elements of the contents in the stored array are used as the input of the mapping function. The output of the mapping function is the location of the stored data. This access speed saves the implementation of traversing the array, so the time complexity can be considered as O( 1), and the time complexity of array traversal is O(n).

The above is the detailed content of What are the four types of data storage structures?. For more information, please follow other related articles on the PHP Chinese website!