Logical structure and physical structure

Logical structure

In a nutshell , Logical structure is the relationship between data . There are four common types of logical structures ： Set structure , Linear structure , A tree structure , Graphic structure .

Set structure

On the surface , There is no deep meaning , That is, the data elements belong to the same set , There is no relationship between individual data elements . As shown in the figure below .

Linear structure

A linear structure is similar to a linear relationship , in other words , There is a one-to-one relationship between data elements in a linear structure . Be careful ： Focus on one to one . As shown in the figure below .

A tree structure

There is a one to many relationship between data elements in the tree structure .（ The graph formed by each element and its relationship is similar to the tree view ）. Be careful ： The relationship is one to many . As shown in the figure below .

Graphic structure

There is a many to many relationship between data elements . As shown in the figure below .

Physical structure

Also called storage structure , Divided into two , One is sequential storage structure and the other is chain storage structure , It refers to the choice of centralized storage or decentralized storage of data in the physical storage space . Suppose that the storage size to be stored is 10G The data of , It is stored in a centralized way, as shown in the figure 3a) Shown , Scattered storage, as shown in the figure 3b） Shown .

If you choose centralized storage , Just use the sequential storage structure ; conversely , Just use chain storage . As for how to choose , It mainly depends on the state of the storage device and the purpose of the data .

We know , Centralized storage （ Sequential storage ）（ The underlying implementation uses arrays ） Need to use a large continuous physical space , Suppose that the storage size to be stored is 1G The data of , If there is no block on the storage device with a size greater than 1G Space , You can't use sequential storage , At this point, you need to select chain storage , Because chained storage is random storage of data , It takes up relatively small storage space in the storage device , Therefore, there is a certain probability that you can store success

also , The purpose of data is different , The storage structure chosen is also different . The centralized storage of data is conducive to the traversal of data in the later stage , Decentralized storage is more conducive to adding or deleting data later . therefore , If you need a lot of data retrieval later （ Traverse ）, Choose centralized storage ; conversely , If the data needs to be further updated later （ Add or delete ）, Then select decentralized storage （ Chain store ）.

There is no conflict between logical structure and physical structure , One refers to the relationship between data , The other refers to the expression of this relationship in the computer . such as , Stack in linear table , The relationship between data elements is one-to-one , Every node, except the head and tail nodes, has a unique precursor and a unique successor , It's a logical structure ; And for nodes in the stack , They can be stored sequentially （ That is, the sequence stack ）, Take a continuous section of storage space , Store stack nodes in order , Each node is physically adjacent to its predecessor and successor . meanwhile , Stack nodes can also be chained （ Chain stack ）, Each node includes data field and pointer field , The pointer field is used to point to its successor , When accessing, you can find the subsequent access through the pointer , Each node can be physically adjacent or not adjacent .