㈠ 數據的存儲結構包括哪四種
存儲結構有：
1、鏈接存儲：在計算機中用一組任意的存儲單元存儲線性表的數據元素（這組存儲單元可以是連續的，也可以是不連續的）。
例：鏈。
2、順序存儲：在計算機中用一組地址連續的存儲單元依次存儲線性表的各個數據元素，稱作線性表的順序存儲結構。
例：數組，鏈。
3、索引存儲：除建立存儲結點信息外，還建立附加的索引表來標識結點的地址，索引表由若干索引項組成。
例：線索樹。
4、散列存儲：散列存儲，又稱hash存儲，是一種力圖將數據元素的存儲位置與關鍵碼之間建立確定對應關系的查找技術。
例：棧（既可以通過順序存儲也可以同通過隨機存儲）。
順序存儲和鏈接存儲的基本原理：
在順序存儲中，每個存儲空間含有所存元素本身的信息，元素之間的邏輯關系是通過數組下標位置簡單計算出來的線性表的順序存儲，若一個元素存儲在對應數組中的下標位置為i，則它的前驅元素在對應數組中的下標位置為i-1，它的後繼元素在對應數組中的下標位置為i+1。
在鏈式存儲結構中，存儲結點不僅含有所存元素本身的信息，而且含有元素之間邏輯關系的信息。
在數據的順序存儲中，由於每個元素的存儲位置都可以通過簡單計算得到，所以訪問元素的時間都相同。
而在數據的鏈接存儲中，由於每個元素的存儲位置保存在它的前驅或後繼結點中，所以只有當訪問到其前驅結點或後繼結點後才能夠按指針訪問到，訪問任一元素的時間與該元素結點在鏈式存儲結構中的位置有關。
㈡ 關於數據結構的問題
應該是A，雙向鏈表就不說了。
首先應該了解存儲表示方法有四種：
◆ 順序存儲方法：它是把邏輯上相鄰的結點存儲在物理位置相鄰的存儲單元里，結點間的邏輯關系由存儲單元的鄰接關系來體現。由此得到的存儲表示稱為順序存儲結構。
◆ 鏈接存儲方法：它不要求邏輯上相鄰的結點在物理位置上亦相鄰，結點間的邏輯關系是由附加的指針欄位表示的。由此得到的存儲表示稱為鏈式存儲結構。
◆ 索引存儲方法：除建立存儲結點信息外，還建立附加的索引表來標識結點的地址。
◆ 散列存儲方法：就是根據結點的關鍵字直接計算出該結點的存儲地址。
閉散列表是應該屬於散列存儲，是哈希演算法的一種處理存儲沖突方式，
當由關鍵碼得到的哈希地址一旦產生了沖突,也就是說,該地址已經存放了數據元素,就去尋找下一個空的哈希地址,只要哈希表足夠大,空的哈希地址總能找到,並將數據元素存入. 所以符合散列存儲方法的要求。
而線索二叉樹是索引存儲，它是對二叉樹以某種方式遍歷後，得到二叉樹中所有結點的一個線性序列。這樣，二叉樹中的結點就有了唯一直接前驅結點和唯一直接後繼結點。
在線索二叉樹時，二叉樹採用二叉鏈表作為存儲結構，每個結點有五個域leftChild,leftTag,data,rightTag,rightChild
規定：如果某結點的左指針域為空，令其指向依某種方式遍歷時所得到的該結點的前驅結點，否則指向左孩子。
如果某結點的右指針域為空，令其指向依某種方式遍歷時所得到的該結點的後繼結點，否則指向右孩子（？？）
為了區分一個結點的指針是指向左右孩子還是指向前驅，後繼結點，可用標志為來區分：
如果 leftTag/rightTag=0,那麼指向左/右孩子。
如果 leftTag/rightTag=1,那麼指向前驅/後繼線索。
對一顆二叉樹的遍歷方法不同，得到的線索二叉樹也不同。通常有前序線索二叉樹，中序線索二叉樹，後序線索二叉樹。
㈢ 資料庫索引的實現原理
資料庫索引的實現原理
一、概述資料庫索引，是資料庫管理系統中一個排序的數據結構，以協助快速查詢、更新資料庫表中數據。索引的實現通常使用B樹及其變種B+樹。在數據之外，資料庫系統還維護著滿足特定查找演算法的數據結構，這些數據結構以某種方式引用(指向)數據，這樣就可以在這些數據結構上實現高級查找演算法。這種數據結構，就是索引。其實說穿了，索引問題就是一個查找問題。二、索引的原理當我們的業務產生了大量的數據時，查找數據的效率問題也就隨之而來，所以我們可以通過為表設置索引，而為表設置索引要付出代價的：一是增加了資料庫的存儲空間，二是在插入和修改數據時要花費較多的時間(因為索引也要隨之變動)。
上圖展示了一種可能的索引方式。左邊是數據表，一共有兩列七條記錄，最左邊的是數據記錄的物理地址(注意邏輯上相鄰的記錄在磁碟上也並不是一定物理相鄰的)。為了加快Col2的查找，可以維護一個右邊所示的二叉查找樹，每個節點分別包含索引鍵值和一個指向對應數據記錄物理地址的指針，這樣就可以運用二叉查找在O(log2n)的復雜度內獲取到相應數據。索引是建立在資料庫表中的某些列的上面。在創建索引的時候，應該考慮在哪些列上可以創建索引，在哪些列上不能創建索引。一般來說，應該在這些列上創建索引：在經常需要搜索的列上，可以加快搜索的速度;在作為主鍵的列上，強制該列的唯一性和組織表中數據的排列結構;在經常用在連接的列上，這些列主要是一些外鍵，可以加快連接的速度;在經常需要根據范圍進行搜索的列上創建索引，因為索引已經排序，其指定的范圍是連續的;在經常需要排序的列上創建索引，因為索引已經排序，這樣查詢可以利用索引的排序，加快排序查詢時間;在經常使用在WHERE子句中的列上面創建索引，加快條件的判斷速度。創建索引可以大大提高系統的性能第一，通過創建唯一性索引，可以保證資料庫表中每一行數據的唯一性。第二，可以大大加快數據的檢索速度，這也是創建索引的最主要的原因。第三，可以加速表和表之間的連接，特別是在實現數據的參考完整性方面特別有意義。第四，在使用分組和排序子句進行數據檢索時，同樣可以顯著減少查詢中分組和排序的時間。第五，通過使用索引，可以在查詢的過程中，使用優化隱藏器，提高系統的性能。也許會有人要問：增加索引有如此多的優點，為什麼不對表中的每一個列創建一個索引呢?因為，增加索引也有許多不利的方面。創建索引的弊端第一，創建索引和維護索引要耗費時間，這種時間隨著數據量的增加而增加。第二，索引需要佔物理空間，除了數據表占數據空間之外，每一個索引還要佔一定的物理空間，如果要建立聚簇索引，那麼需要的空間就會更大。第三，當對表中的數據進行增加、刪除和修改的時候，索引也要動態的維護，這樣就降低了數據的維護速度。同樣，對於有些列不應該創建索引。一般來說，不應該創建索引的的這些列具有下列特點：第一，對於那些在查詢中很少使用或者參考的列不應該創建索引。這是因為，既然這些列很少使用到，因此有索引或者無索引，並不能提高查詢速度。相反，由於增加了索引，反而降低了系統的維護速度和增大了空間需求。第二，對於那些只有很少數據值的列也不應該增加索引。這是因為，由於這些列的取值很少，例如人事表的性別列，在查詢的結果中，結果集的數據行佔了表中數據行的很大比例，即需要在表中搜索的數據行的比例很大。增加索引，並不能明顯加快檢索速度。第三，對於那些定義為text, image和bit數據類型的列不應該增加索引。這是因為，這些列的數據量要麼相當大，要麼取值很少。第四，當修改性能遠遠大於檢索性能時，不應該創建索引。這是因為，修改性能和檢索性能是互相矛盾的。當增加索引時，會提高檢索性能，但是會降低修改性能。當減少索引時，會提高修改性能，降低檢索性能。因此，當修改性能遠遠大於檢索性能時，不應該創建索引。三、索引的類型根據資料庫的功能，可以在資料庫設計器中創建三種索引：唯一索引、主鍵索引和聚集索引。唯一索引唯一索引是不允許其中任何兩行具有相同索引值的索引。當現有數據中存在重復的鍵值時，大多數資料庫不允許將新創建的唯一索引與表一起保存。資料庫還可能防止添加將在表中創建重復鍵值的新數據。例如，如果在employee表中職員的姓(lname)上創建了唯一索引，則任何兩個員工都不能同姓。主鍵索引資料庫表經常有一列或列組合，其值唯一標識表中的每一行。該列稱為表的主鍵。在資料庫關系圖中為表定義主鍵將自動創建主鍵索引，主鍵索引是唯一索引的特定類型。該索引要求主鍵中的每個值都唯一。當在查詢中使用主鍵索引時，它還允許對數據的快速訪問。聚集索引在聚集索引中，表中行的物理順序與鍵值的邏輯(索引)順序相同。一個表只能包含一個聚集索引。如果某索引不是聚集索引，則表中行的物理順序與鍵值的邏輯順序不匹配。與非聚集索引相比，聚集索引通常提供更快的數據訪問速度。四、局部性原理與磁碟預讀由於存儲介質的特性，磁碟本身存取就比主存慢很多，再加上機械運動耗費，磁碟的存取速度往往是主存的幾百分分之一，因此為了提高效率，要盡量減少磁碟I/O。為了達到這個目的，磁碟往往不是嚴格按需讀取，而是每次都會預讀，即使只需要一個位元組，磁碟也會從這個位置開始，順序向後讀取一定長度的數據放入內存。這樣做的理論依據是計算機科學中著名的局部性原理：當一個數據被用到時，其附近的數據也通常會馬上被使用。程序運行期間所需要的數據通常比較集中。由於磁碟順序讀取的效率很高(不需要尋道時間，只需很少的旋轉時間)，因此對於具有局部性的程序來說，預讀可以提高I/O效率。預讀的長度一般為頁(page)的整倍數。頁是計算機管理存儲器的邏輯塊，硬體及操作系統往往將主存和磁碟存儲區分割為連續的大小相等的塊，每個存儲塊稱為一頁(在許多操作系統中，頁得大小通常為4k)，主存和磁碟以頁為單位交換數據。當程序要讀取的數據不在主存中時，會觸發一個缺頁異常，此時系統會向磁碟發出讀盤信號，磁碟會找到數據的起始位置並向後連續讀取一頁或幾頁載入內存中，然後異常返回，程序繼續運行。五、B樹和B+樹數據結構1、B樹B樹中每個節點包含了鍵值和鍵值對於的數據對象存放地址指針，所以成功搜索一個對象可以不用到達樹的葉節點。成功搜索包括節點內搜索和沿某一路徑的搜索，成功搜索時間取決於關鍵碼所在的層次以及節點內關鍵碼的數量。在B樹中查找給定關鍵字的方法是：首先把根結點取來，在根結點所包含的關鍵字K1,…,kj查找給定的關鍵字(可用順序查找或二分查找法)，若找到等於給定值的關鍵字，則查找成功;否則，一定可以確定要查的關鍵字在某個Ki或Ki+1之間，於是取Pi所指的下一層索引節點塊繼續查找，直到找到，或指針Pi為空時查找失敗。2、B+樹B+樹非葉節點中存放的關鍵碼並不指示數據對象的地址指針，非也節點只是索引部分。所有的葉節點在同一層上，包含了全部關鍵碼和相應數據對象的存放地址指針，且葉節點按關鍵碼從小到大順序鏈接。如果實際數據對象按加入的順序存儲而不是按關鍵碼次數存儲的話，葉節點的索引必須是稠密索引，若實際數據存儲按關鍵碼次序存放的話，葉節點索引時稀疏索引。B+樹有2個頭指針，一個是樹的根節點，一個是最小關鍵碼的葉節點。所以 B+樹有兩種搜索方法：一種是按葉節點自己拉起的鏈表順序搜索。一種是從根節點開始搜索，和B樹類似，不過如果非葉節點的關鍵碼等於給定值，搜索並不停止，而是繼續沿右指針，一直查到葉節點上的關鍵碼。所以無論搜索是否成功，都將走完樹的所有層。B+ 樹中，數據對象的插入和刪除僅在葉節點上進行。這兩種處理索引的數據結構的不同之處：1、B樹中同一鍵值不會出現多次，並且它有可能出現在葉結點，也有可能出現在非葉結點中。而B+樹的鍵一定會出現在葉結點中，並且有可能在非葉結點中也有可能重復出現，以維持B+樹的平衡。2、因為B樹鍵位置不定，且在整個樹結構中只出現一次，雖然可以節省存儲空間，但使得在插入、刪除操作復雜度明顯增加。B+樹相比來說是一種較好的折中。3、B樹的查詢效率與鍵在樹中的位置有關，最大時間復雜度與B+樹相同(在葉結點的時候)，最小時間復雜度為1(在根結點的時候)。而B+樹的時候復雜度對某建成的樹是固定的。六、B/+Tree索引的性能分析到這里終於可以分析B-/+Tree索引的性能了。上文說過一般使用磁碟I/O次數評價索引結構的優劣。先從B-Tree分析，根據B-Tree的定義，可知檢索一次最多需要訪問h個節點。資料庫系統的設計者巧妙利用了磁碟預讀原理，將一個節點的大小設為等於一個頁，這樣每個節點只需要一次I/O就可以完全載入。為了達到這個目的，在實際實現B-Tree還需要使用如下技巧：每次新建節點時，直接申請一個頁的空間，這樣就保證一個節點物理上也存儲在一個頁里，加之計算機存儲分配都是按頁對齊的，就實現了一個node只需一次I/O。B-Tree中一次檢索最多需要h-1次I/O(根節點常駐內存)，漸進復雜度為O(h)=O(logdN)。一般實際應用中，出度d是非常大的數字，通常超過100，因此h非常小(通常不超過3)。而紅黑樹這種結構，h明顯要深的多。由於邏輯上很近的節點(父子)物理上可能很遠，無法利用局部性，所以紅黑樹的I/O漸進復雜度也為O(h)，效率明顯比B-Tree差很多。綜上所述，用B-Tree作為索引結構效率是非常高的。
㈣ 什麼是系統中存放數據的基本方式
1、順序存儲方式：順序存儲方式就是在一塊連續的存儲區域一個接著一個的存放數據。順序存儲方式把邏輯上相鄰的節點存儲在物理位置撒花姑娘相鄰的存儲單元里，節點間的邏輯關系由存儲單元的鄰接關系來體現。順序存儲方式也稱為順序存儲結構，一般採用數組或結構數組來描述。
2、鏈接存儲方式：鏈接存儲方式比較靈活，不要求邏輯上相鄰的節點在物理位置上相鄰，節點間的邏輯關系由附加的引用欄位來表示。一個節點的引用欄位往往指向下一個節點的存放位置。鏈接存儲方式也成為鏈式存儲結構。
3、索引存儲方式：索引存儲方式是採用附加的索引表的方式來存儲節點信息的一種存儲方式。索引表由若干索引項組成。索引存儲方式中索引項的一般形式為(關鍵字、地址)。其中，關鍵字是能夠唯一標識一個節點的數據項。索引存儲方式還可以細分為如下兩類。
稠密索引：這種方式中每個節點在索引表中都有一個索引項，其中索引項的地址知識節點所在的存儲位置。
稀疏索引：這種方式中一組節點在索引表中只對應一個索引項。其中，索引項的地址指示一組節點的起始存儲位置。
4、散列存儲方式：散列存儲方式是根據節點的關鍵字直接計算出該節點的存儲地址的一種存儲方式。
在實際應用中，往往需要根據具體的數據結構來決定採用哪種存儲方式。同一邏輯結構採用不同的存儲方法，可以得到不同的存儲結構。而且者4中基本存儲方法，既可以單獨使用，也可以組合起來對數據結構進行存儲描述。
㈤ 數據結構中散列存儲和索引存儲的區別！求教 最好能生動點
散列存儲是直接將關鍵字的值做一個映射到存儲地址
索引存儲則是另外使用關鍵字來構建一個索引表（也可以是單級，也可以是多級的），先在索引表中找到存儲位置後，再訪問內容
㈥ 資料庫基礎：講解MySQL索引的概念及資料庫索引的應用[1]
資料庫引入了索引
用戶對資料庫最頻繁的操作是進行數據查詢 一般情況下 資料庫在進行查詢操作時需要對整個表進行數據搜索 當表中的數據很多時 搜索數據就需要很長的時間 這就造成了伺服器的資源浪費 為了提高檢索數據的能力 資料庫引入了索引機制
有關 索引 的比喻
從某種程度上 可以把資料庫看作一本書 把索引看作書的目錄 通過目錄查找書中的信息 顯然較沒有目錄的書方便 快捷
資料庫索引實際是什麼告滲?(兩部分組成)
索引是一個單獨的 物理的資料庫結構 它是某個表中一列或若干列值的集合和相應的指向表中物理標識這些值的數據頁的邏輯指針清單
索引在表中的角色
一個表的存儲是由兩部分組成的 一部分用來存放表的數據頁面 另一部分存放索引頁面 索引就存放在索引頁面上
索引高效原理
通常 索引頁面相對於數據頁面來說小得多 當進行數據檢索時 系統先搜索索引頁面 從中找到所需數據的指針 再直接通過指針從數據頁面中讀取數據
索引的分類
在SQL Server 的資料庫中按存儲結構的不同將索引分為兩類 簇索引(Clustered Index)和非簇索引(Nonclustered Index)
( )簇索引對表的物理數據頁中的數據按列進行排序 然後再重新存儲到磁碟上 即簇索引與數據是混為一體 的它的葉節點中存儲的是實際的數據 由於簇索引對表中的數據一一進行了排序 因此用簇索引查找數據很快 但由於簇索引將表的所有數據完全重新排列了 它所需要的空間也就特別大 大概相當於表中數據所佔空間的 % 表的數據行只能以一種排序方式存儲在磁碟上 所以一個表只能有一個簇索引
( )非簇索引具有與表的數據完全分離的結構 使用非簇索引不用將物理數據頁中的數據按列襪友鍵排序 非簇索引的葉節點中存儲了組成非簇索引的關鍵字的值和行定位器 行定位器的結構和存儲內容取決於數據的存儲方式 如果數據是以簇索引方式存儲的 則行定位器中存儲的是簇索引的索引鍵;如果數據不是以簇索引方式存儲的 這種方式又稱為堆存儲方式(Heap Structure) 則行定位器存儲的是指向數據行的指針 非簇索引將行定位器按關鍵字的值用一定的方式排序 這個順序與表的行在數據頁中的排序是不匹配的 由於非簇索引使用索引頁存儲因此它比簇索引需要更多的存儲空間且檢索效率較低但一個表只能建一個簇索引 當用戶需要建立多個索引時就需要使用非簇索引了
小結 Clustered Index 是與物理數據混在一起並對物理數據進重排 就像使用拼音查字典;Unclustered Index 是與物理數據完全分離的 利用額外空間對關鍵字進行重排 就像使用部首查字典
資料庫索引應用
一 索引的概念
索引就是加快檢索表中數據的方法 資料庫的索引類似於書籍的索引 在書籍中 索引允許用戶不必翻閱完整個書就能迅速地找到所需要的信息 在資料庫中 索引也允許資料庫程序迅速地找到表中的數據 而不必掃描整個資料庫
二 索引的特點
索引可以加快資料庫的檢索速度
索引降低了資料庫插入 修改 刪除等維護任務的速度
索引創建在表上 不能創建在視圖上
索引既可以直接創建 也可以間接創建
可以在優化隱藏中 使用索引
使用查詢處理器執行SQL語句 在一個表上 一次只能使用一個索引
其他
三 索引的優點
創建唯一性索引 保證資料庫表中每一行數據的唯一性
大大加快數據的檢索速度 這也是創建索引的最主要的原因
加速表和表之間的連接 特別是在實現數據的參考完整性方面特別有意義
在使用分組和排序子句進行數據檢索時 同樣可以顯著減少查詢中分組和排序的時間
通過使用索引 可以在查詢告巧的過程中使用優化隱藏器 提高系統的性能
四 索引的缺點
創建索引和維護索引要耗費時間 這種時間隨著數據量的增加而增加
索引需要佔物理空間 除了數據表占數據空間之外 每一個索引還要佔一定的物理空間 如果要建立聚簇索引 那麼需要的空間就會更大
當對表中的數據進行增加 刪除和修改的時候 索引也要動態的維護 降低了數據的維護速度
lishixin/Article/program/MySQL/201311/29604