Shulou(Shulou.com)06/03 Report--

This article mainly explains the "physical storage structure of java data structure". The explanation in this article is simple and clear, easy to learn and understand. Please follow the ideas of Xiaobian and go deep into it slowly to study and learn the "physical storage structure of java data structure" together!

text

A physical storage structure is the logical structure of data stored in a computer.

But before we understand the physical structure of data storage, we need to have a good understanding of hard disks.

A hard disk is an actual object, which means that it cannot store our data as logically designed as we imagine. Imagine if we stored a million pieces of data randomly on our hard disk, not according to objective physical rules, and we would find that hard disk space would be wasted.

Therefore, when storing data in the hard disk, we must follow certain objective laws. And this objective law, in the process of computer development, gradually formed two kinds of laws that are more common now.

1. sequential storage structure

Sequential storage structure is to store adjacent data in our logical data structure in adjacent locations in physical locations. Node relationships in a data structure are represented by adjacency relationships of memory cells.

In other words, logical and physical relationships between data are consistent.

Generally speaking, in our java language, describing this physical storage structure is explained by means of our arrays. As shown in the figure:

This storage structure was easy to understand. To put it bluntly, it was just queuing. Each piece of data occupied a small space and stood in order, occupying a continuous storage space.

1.1 advantages

The advantages of sequential storage structure are still relatively obvious, because the data is stored in the order of physical storage space, then the utilization of storage space will be very high, and the storage density is relatively large.

And because we store data sequentially, that is to say, when our data is stored here, it will naturally be much faster in the average seek time on the hard disk.

So, what is seek time? Let's start with a picture of the disk, as follows:

We found that in this traditional hard disk, data is stored in tracks on the disk (disk platter), and the data is searched by the head (read/write head). The average seek time is the average of the time it takes the head to move to the track where the data is located.

If the seek speed of the hard disk is getting faster, it means that our ability to find data is also getting faster.

In our sequential storage structure, our data is stored on the tracks in the rotation order of the tracks, that is, when we search for data, we will locate the actual data faster, which means that our data search speed is faster.

Little knowledge;

In the modern computer evolution process, data storage has changed a lot, such as we are now more common solid-state hard disk, because SSD solid-state hard disk has no head, so almost no seek time this concept, when the system issues instructions, do not need a head and disk, but directly from the Flash particles read, compared to the traditional mechanical hard disk seek time is much faster.

The advantages of sequential storage structure are summarized as follows:

Data storage density is large, and the utilization rate of storage space is large.

Search speed is faster.

1.2 disadvantages

The first thing we know is that the sequential storage structure, the stored data, in the storage space, is continuous, as shown in the following figure;

So what happens when we insert a piece of data? As shown in the figure:

From the insertion process shown in the figure, we found that since the insertion position, all the data elements behind have moved one bit to the back. Think about it, if the amount of data goes up, then a large amount of data has to be moved, and the actual situation is far worse than this, so the insertion efficiency can be imagined.

The deletion process, although the opposite of insertion, but the consequences are the same, both will lead to a large number of data shift location.

Therefore, what we know is that the disadvantage of sequential storage structure is that it is inefficient when inserting or deleting.

2. chain storage structure

In the actual data operation process, some data structures need to be faster when searching, then our sequential storage structure is in line with this requirement, but there are also many times, our data will be deleted many times and inserted many times, which causes a problem. The sequential storage structure cannot meet this demand scenario, so there is a chain storage structure.

Chained storage structures store data elements in arbitrary storage units, which can be contiguous or discontinuous.

That is to say, in the chain storage structure, data can be placed in any position of this storage space, and therefore, the relationship between the physical location of data and data cannot express the logical relationship between data.

So how do you resolve this logical relationship?

Thus, in a chained storage structure, a data unit is divided into two areas, a data area and a pointer area.

The data field stores our actual data, while the pointer field stores pointers to the locations of other associated data. If you want to store data [A , B , C , D , E] through a chain storage structure, the approximate model stored is as shown in the figure:

On the basis of this graph, after transformation, the graph becomes the following: In this way, it can be seen that the pointer field points to the next data node, that is, in the continuous storage structure, the relationship between data is represented by the pointing relationship of the pointer field, and has nothing to do with the actual storage location of the data.

2.1 advantages

The advantages of chained storage structure are well understood. First, look at the insertion diagram of chained storage structure:

Because in the chain storage structure, the relationship of data is not represented by the actual storage location of the data, but by the pointer field of each data node, that is to say, when inserting or deleting data, there is no need to move the data behind the inserted data, only need to modify the directivity of the pointer field.

That is to say, the insertion or deletion of elements in the chain storage structure is very convenient and flexible. And what we see is that the chain storage structure does not require continuous memory to store, that is, the utilization efficiency of fragmented memory is relatively high.

2.2 disadvantages

In a sequential storage structure, data storage requires only that data be stored. However, in the chain storage structure, the storage of data, in addition to storing this data, also needs to store the pointer field related to this data.

In this way, compared with the sequential storage structure, the chain storage structure stores a part of other data, so the utilization rate of storage space will be reduced.

Moreover, it should be noted that the chain storage structure, in terms of physical logic, because the actual storage location is not sequential, then when reading, the efficiency will be relatively low.

Summary 3.1 Sequential Storage Structure

Advantages:

Data storage density is large, and the utilization rate of storage space is large.

Search speed is faster. Disadvantages:

When inserting or deleting, the efficiency will be relatively low.

3.2 chain storage structure

Advantages:

When inserting or deleting, it is more efficient.

High memory utilization for fragmentation. Disadvantages:

Additional pointer field data added, large memory consumption

It's less efficient when it comes to reading.

Thank you for reading, the above is the "java data structure on the physical storage structure" of the content, after learning this article, I believe we have a deeper understanding of the java data structure on the physical storage structure of this issue, the specific use of the situation also needs to be verified by practice. Here is, Xiaobian will push more articles related to knowledge points for everyone, welcome to pay attention!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.