基本介紹
- 中文名：存儲結構
- 分類：順序存儲結構 鏈式存儲結構
數據結構方面的儲存結構,分類,順序存儲和連結存儲的基本原理,儲存器方面的儲存結構,程式的局部性原理,多級存儲體系的組成,
數據結構方面的儲存結構
分類
順序存儲方法它是把邏輯上相鄰的結點存儲在物理位置相鄰的存儲單元里，結點間的邏輯關係由存儲單元的鄰接關係來體現，由此得到的存儲表示稱為順序存儲結構。順序存儲結構是一種最基本的存儲表示方法，通常藉助於程式設計語言中的數組來實現。
順序存儲和連結存儲的基本原理
順序存儲和連結存儲是數據的兩種最基本的存儲結構。
在順序存儲中，每個存儲空間含有所存元素本身的信息，元素之間的邏輯關係是通過數組下標位置簡單計算出來的線性表的順序存儲，若一個元素存儲在對應數組中的下標位置為i，則它的前驅元素在對應數組中的下標位置為i-1，它的後繼元素在對應數組中的下標位置為i+1。在鏈式存儲結構中，存儲結點不僅含有所存元素本身的信息，而且含有元素之間邏輯關係的信息。
數據的鏈式存儲結構可用連結表來表示。
其中data表示值域，用來存儲節點的數值部分。Pl，p2，…，Pill(1n≥1)均為指針域，每個指針域為其對應的後繼元素或前驅元素所在結點(以後簡稱為後繼結點或前驅結點)的存儲位置。通過結點的指針域(又稱為鏈域)可以訪問到對應的後繼結點或前驅結點，若一個結點中的某個指針域不需要指向其他結點，則令它的值為空（NULL）。
在數據的順序存儲中，由於每個元素的存儲位置都可以通過簡單計算得到，所以訪問元素的時間都相同；而在數據的連結存儲中，由於每個元素的存儲位置保存在它的前驅或後繼結點中，所以只有當訪問到其前驅結點或後繼結點後才能夠按指針訪問到，訪問任一元素的時間與該元素結點在鏈式存儲結構中的位置有關。
儲存器方面的儲存結構
程式的局部性原理
在某一段時間內，CPU頻繁訪問某一局部的存儲器區域，而對此範圍外的地址則較少訪問的現象就是
程式的局部性原理。層次結構是基於程式的局部性原理的。對大量典型程式運行情況的統計分析得出的結論是：CPU對某些地址的訪問在短時間間隔內出現集中分布的傾向。這有利於對存儲器實現層次結構。
多級存儲體系的組成
目前，大多採用三級存儲結構。
即：Cache-主存-輔存，如下圖：
3、多級存儲系統的性能
考慮由Cache和主存構成的兩級存儲系統，其性能主要取決於Cache和貯存的存取周期以及訪問它們的
次數。（存取周期為: Tc,Tm ;訪問次數為: Nc,Nm）
（1）Cache的命中率 H= Nc / (Nc+Nm)
（2）CPU訪存的平均時間 Ta= H * Tc+ (1-H) Tm
Cache-主存系統的效率
e= Tc / Ta
=1/H+(1-H)Tm/Tc
根據統計分析：Cache的命中率可以達到90%~98%
當Cache的容量為：32KB時，命中率為86%
64KB時，命中率為92%
128KB時，命中率為95%
256KB時，命中率為98%
