索引的實現演算法

Ⅰ 資料庫索引的實現原理

資料庫索引的實現原理
一、概述資料庫索引，是資料庫管理系統中一個排序的數據結構，以協助快速查詢、更新資料庫表中數據。索引的實現通常使用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作為索引結構效率是非常高的。

Ⅱ mysql的索引用的什麼數據結構

談到索引，大家並不陌生。索引本身是一種數據結構，存在的目的主要是為了縮短數據檢索的時間，最大程度減少磁碟 IO。
任何有數據的場景幾乎都有索引，比如手機通訊錄、文件系統（ext4\xfs\ntfs)、資料庫系統（MySQL\Oracle）。資料庫系統和文件系統一般都採用 B+ 樹來存儲索引信息，B+ 樹兼顧寫和讀的性能，最極端時檢索復雜度為 O(logN)，其中 N 指的是節點數量，logN 表示對磁碟 IO 掃描的總次數。
MySQL 支持的索引結構有四種：B+ 樹，R 樹，HASH，FULLTEXT。

Ⅲ 索引的原理

索引是一種利用某種規則的數據結構與實際數據的關系加快數據查找的功能;索引數據節點中有著實際文件的位置,因為索引是根據特定的規則和演算法構建的,在查找的時候遵循索引的規則可以快速查找到對應數據的節點,從而達到快速查找數據的效果。

Ⅳ 搜索引擎的排序演算法都有哪些是怎麼實現的

2.1基於詞頻統計——詞位置加權的搜索引擎
利用關鍵詞在文檔中出現的頻率和位置排序是搜索引擎最早期排序的主要思想，其技術發展也最為成熟，是第一階段搜索引擎的主要排序技術，應用非常廣泛，至今仍是許多搜索引擎的核心排序技術。其基本原理是：關鍵詞在文檔中詞頻越高，出現的位置越重要，則被認為和檢索詞的相關性越好。
1）詞頻統計
文檔的詞頻是指查詢關鍵詞在文檔中出現的頻率。查詢關鍵詞詞頻在文檔中出現的頻率越高，其相關度越大。但當關鍵詞為常用詞時，使其對相關性判斷的意義非常小。TF/IDF很好的解決了這個問題。TF/IDF演算法被認為是信息檢索中最重要的發明。TF（Term Frequency）：單文本詞彙頻率，用關鍵詞的次數除以網頁的總字數，其商稱為「關鍵詞的頻率」。IDF（Inverse Document Frequency）：逆文本頻率指數，其原理是，一個關鍵詞在N個網頁中出現過，那麼N越大，此關鍵詞的權重越小，反之亦然。當關鍵詞為常用詞時，其權重極小，從而解決詞頻統計的缺陷。
2）詞位置加權
在搜索引擎中，主要針對網頁進行詞位置加權。所以，頁面版式信息的分析至關重要。通過對檢索關鍵詞在Web頁面中不同位置和版式，給予不同的權值，從而根據權值來確定所搜索結果與檢索關鍵詞相關程度。可以考慮的版式信息有：是否是標題，是否為關鍵詞，是否是正文，字體大小，是否加粗等等。同時，錨文本的信息也是非常重要的，它一般能精確的描述所指向的頁面的內容。
2.2基於鏈接分析排序的第二代搜索引擎
鏈接分析排序的思想起源於文獻引文索引機制，即論文被引用的次數越多或被越權威的論文引用，其論文就越有價值。鏈接分析排序的思路與其相似，網頁被別的網頁引用的次數越多或被越權威的網頁引用，其價值就越大。被別的網頁引用的次數越多，說明該網頁越受歡迎，被越權威的網頁引用，說明該網頁質量越高。鏈接分析排序演算法大體可以分為以下幾類：基於隨機漫遊模型的，比如PageRank和Repution演算法；基於概率模型的，如SALSA、PHITS；基於Hub和Authority相互加強模型的，如HITS及其變種；基於貝葉斯模型的，如貝葉斯演算法及其簡化版本。所有的演算法在實際應用中都結合傳統的內容分析技術進行了優化。本文主要介紹以下幾種經典排序演算法：
1）PageRank演算法
PageRank演算法由斯坦福大學博士研究生Sergey Brin和Lwraence Page等提出的。PageRank演算法是Google搜索引擎的核心排序演算法，是Google成為全球最成功的搜索引擎的重要因素之一，同時開啟了鏈接分析研究的熱潮。
PageRank演算法的基本思想是：頁面的重要程度用PageRank值來衡量，PageRank值主要體現在兩個方面：引用該頁面的頁面個數和引用該頁面的頁面重要程度。一個頁面P（A）被另一個頁面P（B）引用，可看成P（B）推薦P（A），P（B）將其重要程度（PageRank值）平均的分配P（B）所引用的所有頁面，所以越多頁面引用P（A），則越多的頁面分配PageRank值給P（A），PageRank值也就越高，P（A）越重要。另外，P(B)越重要，它所引用的頁面能分配到的PageRank值就越多，P（A）的PageRank值也就越高，也就越重要。
其計算公式為：

PR（A）：頁面A的PageRank值；
d：阻尼系數，由於某些頁面沒有入鏈接或者出鏈接，無法計算PageRank值，為避免這個問題（即LinkSink問題），而提出的。阻尼系數常指定為0.85。
R（Pi）：頁面Pi的PageRank值；
C（Pi）：頁面鏈出的鏈接數量；
PageRank值的計算初始值相同，為了不忽視被重要網頁鏈接的網頁也是重要的這一重要因素，需要反復迭代運算，據張映海撰文的計算結果，需要進行10次以上的迭代後鏈接評價值趨於穩定，如此經過多次迭代，系統的PR值達到收斂。
PageRank是一個與查詢無關的靜態演算法，因此所有網頁的PageRank值均可以通過離線計算獲得。這樣，減少了用戶檢索時需要的排序時間，極大地降低了查詢響應時間。但是PageRank存在兩個缺陷：首先PageRank演算法嚴重歧視新加入的網頁，因為新的網頁的出鏈接和入鏈接通常都很少，PageRank值非常低。另外PageRank演算法僅僅依靠外部鏈接數量和重要度來進行排名，而忽略了頁面的主題相關性，以至於一些主題不相關的網頁（如廣告頁面）獲得較大的PageRank值，從而影響了搜索結果的准確性。為此，各種主題相關演算法紛紛涌現，其中以以下幾種演算法最為典型。
2）Topic-Sensitive PageRank演算法
由於最初PageRank演算法中是沒有考慮主題相關因素的，斯坦福大學計算機科學系Taher Haveli-wala提出了一種主題敏感（Topic-Sensitive）的PageRank演算法解決了「主題漂流」問題。該演算法考慮到有些頁面在某些領域被認為是重要的，但並不表示它在其它領域也是重要的。
網頁A鏈接網頁B，可以看作網頁A對網頁B的評分，如果網頁A與網頁B屬於相同主題，則可認為A對B的評分更可靠。因為A與B可形象的看作是同行，同行對同行的了解往往比不是同行的要多，所以同行的評分往往比不是同行的評分可靠。遺憾的是TSPR並沒有利用主題的相關性來提高鏈接得分的准確性。
3）HillTop演算法
HillTop是Google的一個工程師Bharat在2001年獲得的專利。HillTop是一種查詢相關性鏈接分析演算法，克服了的PageRank的查詢無關性的缺點。HillTop演算法認為具有相同主題的相關文檔鏈接對於搜索者會有更大的價值。在Hilltop中僅考慮那些用於引導人們瀏覽資源的專家頁面（Export Sources）。Hilltop在收到一個查詢請求時，首先根據查詢的主題計算出一列相關性最強的專家頁面，然後根據指向目標頁面的非從屬專家頁面的數量和相關性來對目標頁面進行排序。
HillTop演算法確定網頁與搜索關鍵詞的匹配程度的基本排序過程取代了過分依靠PageRank的值去尋找那些權威頁面的方法，避免了許多想通過增加許多無效鏈接來提高網頁PageRank值的作弊方法。HillTop演算法通過不同等級的評分確保了評價結果對關鍵詞的相關性，通過不同位置的評分確保了主題（行業）的相關性，通過可區分短語數防止了關鍵詞的堆砌。
但是，專家頁面的搜索和確定對演算法起關鍵作用，專家頁面的質量對演算法的准確性起著決定性作用，也就忽略了大多數非專家頁面的影響。專家頁面在互聯網中占的比例非常低（1.79%），無法代表互聯網全部網頁，所以HillTop存在一定的局限性。同時，不同於PageRank演算法，HillTop演算法的運算是在線運行的，對系統的響應時間產生極大的壓力。
4）HITS
HITS（Hyperlink Inced Topic Search）演算法是Kleinberg在1998年提出的，是基於超鏈接分析排序演算法中另一個最著名的演算法之一。該演算法按照超鏈接的方向，將網頁分成兩種類型的頁面：Authority頁面和Hub頁面。Authority頁面又稱權威頁面，是指與某個查詢關鍵詞和組合最相近的頁面，Hub頁面又稱目錄頁，該頁面的內容主要是大量指向Authority頁面的鏈接，它的主要功能就是把這些Authority頁面聯合在一起。對於Authority頁面P，當指向P的Hub頁面越多，質量越高，P的Authority值就越大；而對於Hub頁面H，當H指向的Authority的頁面越多，Authority頁面質量越高，H的Hub值就越大。對整個Web集合而言，Authority和Hub是相互依賴、相互促進，相互加強的關系。Authority和Hub之間相互優化的關系，即為HITS演算法的基礎。
HITS基本思想是：演算法根據一個網頁的入度（指向此網頁的超鏈接）和出度（從此網頁指向別的網頁）來衡量網頁的重要性。在限定范圍之後根據網頁的出度和入度建立一個矩陣，通過矩陣的迭代運算和定義收斂的閾值不斷對兩個向量Authority和Hub值進行更新直至收斂。
實驗數據表明，HITS的排名准確性要比PageRank高，HITS演算法的設計符合網路用戶評價網路資源質量的普遍標准，因此能夠為用戶更好的利用網路信息檢索工具訪問互聯網資源帶來便利。
但卻存在以下缺陷：首先，HITS演算法只計算主特徵向量，處理不好主題漂移問題；其次，進行窄主題查詢時，可能產生主題泛化問題；第三，HITS演算法可以說一種實驗性質的嘗試。它必須在網路信息檢索系統進行面向內容的檢索操作之後，基於內容檢索的結果頁面及其直接相連的頁面之間的鏈接關系進行計算。盡管有人嘗試通過演算法改進和專門設立鏈接結構計算伺服器（Connectivity Server）等操作，可以實現一定程度的在線實時計算，但其計算代價仍然是不可接受的。
2.3基於智能化排序的第三代搜索引擎
排序演算法在搜索引擎中具有特別重要的地位，目前許多搜索引擎都在進一步研究新的排序方法，來提升用戶的滿意度。但目前第二代搜索引擎有著兩個不足之處，在此背景下，基於智能化排序的第三代搜索引擎也就應運而生。
1）相關性問題
相關性是指檢索詞和頁面的相關程度。由於語言復雜，僅僅通過鏈接分析及網頁的表面特徵來判斷檢索詞與頁面的相關性是片面的。例如：檢索「稻瘟病」，有網頁是介紹水稻病蟲害信息的，但文中沒有「稻瘟病」這個詞，搜索引擎根本無法檢索到。正是以上原因，造成大量的搜索引擎作弊現象無法解決。解決相關性的的方法應該是增加語意理解，分析檢索關鍵詞與網頁的相關程度，相關性分析越精準，用戶的搜索效果就會越好。同時，相關性低的網頁可以剔除，有效地防止搜索引擎作弊現象。檢索關鍵詞和網頁的相關性是在線運行的，會給系統相應時間很大的壓力，可以採用分布式體系結構可以提高系統規模和性能。
2）搜索結果的單一化問題
在搜索引擎上，任何人搜索同一個詞的結果都是一樣。這並不能滿足用戶的需求。不同的用戶對檢索的結果要求是不一樣的。例如：普通的農民檢索「稻瘟病」，只是想得到稻瘟病的相關信息以及防治方法，但農業專家或科技工作者可能會想得到稻瘟病相關的論文。
解決搜索結果單一的方法是提供個性化服務，實現智能搜索。通過Web數據挖掘，建立用戶模型（如用戶背景、興趣、行為、風格），提供個性化服務。

Ⅳ 演算法與數據結構 索引查找的實現

二分查找法、哈希查找法、二叉排序樹查找法等各種查找演算法。1. 線性表上的查找： 主要分為三種線性結構：順序表，有序順序表，索引順序表。對於第一種，我們採用傳統查找方法，逐個比較。對於及有序順序表我們採用二分查找法。對於第三種索引結構，我們採用索引查找演算法。其中，二分查找還要特別注意適用條件以及其遞歸實現方法。 2.樹表上的查找： 樹表主要分為以下幾種：二叉排序樹，平衡二叉樹，B樹，鍵樹。由於二叉排序樹與平衡二叉樹是一種特殊的二叉樹，所以與二叉樹的聯系就更為緊密。 二叉排序樹，它的中序遍歷結果是一個遞增的有序序列。平衡二叉樹是二叉排序樹的優化，其本質也是一種二叉排序樹，只不過，平衡二叉樹對左右子樹的深度有了限定。 B樹是二叉排序樹的進一步改進，也可以把B樹理解為三叉、四叉....排序樹。因為這兩種演算法涉及到B樹結點的分裂和合並，是一個難點。鍵樹也稱字元樹，特別適用於查找英文單詞的場合。一般不要求能完整描述演算法源碼，多是根據演算法思想建立鍵樹及描述其大致查找過程。 3.基本哈希表的查找演算法： 哈希表查找的基本思想是：根據當前待查找數據的特徵，以記錄關鍵字為自變數，設計一個function，該函數對關鍵字進行轉換後，其解釋結果為待查的地址。堆排序屬於選擇排序類型的排序，是一樹形選擇排序。堆排序的時間，主要由建立初始堆和反復重建堆這兩部分的時間開銷構成，它們均是通過調用Heapify實現的。 堆排序的最壞時間復雜度為O(nlgn)。堆排序的平均性能較接近於最壞性能。 由於建初始堆所需的比較次數較多，所以堆排序不適宜於記錄數較少的文件。 堆排序是就地排序，輔助空間為O(1)， 它是不穩定的排序方法。堆排序，是利用堆這種數據結構的性質，通過堆元素的刪除、調整等一系列操作將最小數選出放在堆頂。堆排序的特點是：在排序過程中，將R[l..n]看成是一棵完全二叉樹的順序存儲結構，利用完全二叉樹中雙親結點和孩子結點之間的內在關系，在當前無序區中選擇關鍵字最大(或最小)的記錄。堆排序利用了大根堆(或小根堆)堆頂記錄的關鍵字最大(或最小)這一特徵，使得在當前無序區中選取最大(或最小)關鍵字的記錄變得簡單。
vae.la

Ⅵ 從軟體開發的角度看，資料庫的索引有哪幾種傳統的實現方式

在Oracle中的索引可以分為：B樹索引、點陣圖索引、反向鍵索引、基於函數的索引、簇索引、全局索引、局部索引等

Ⅶ 資料庫索引如何實現，邏輯思路

創建索引的條件就是要求你的目標列的行記錄唯一就可以
其他的沒有。
索引也存在效率優化問題但是小數據就不存在。

Ⅷ 索引順序查找演算法

索引查找是在索引表和主表(即線性表的索引存儲結構)上進行的查找。索引查找的過程是：首先根據給定的索引值K1，在索引表上查找出索引值等於KI的索引項，以確定對應予表在主表中的開始位置和長度，然後再根據給定的關鍵字K2，茬對應的子表中查找出關鍵字等於K2的元素(結點)。對索引表或子表進行查找時，若表是順序存儲的有序表，則既可進行順序查找，也可進行二分查找，否則只能進行順序查找。
設數組A是具有mainlist類型的一個主表，數組B是具有inde)dist類型的在主表A 上建立的一個索引表，m為索引表B的實際長度，即所含的索引項的個數，KI和K2分別為給定待查找的索引值和關鍵字(當然它們的類型應分別為索引表中索引值域的類型和主表中關鍵字域在索引存儲中，不僅便於查找單個元素，而且更便於查找一個子表中的全部元素。當需要對一個子袁中的全部元素依次處理時，只要從索引表中查找出該子表的開始位置即可。由此開始位置可以依次取出該子表中的每一個元素，所以整個查找過程的時間復雜度為，若不是採用索引存儲，而是採用順序存儲，即使把它組織成有序表而進行二分查找時，索引查找一個子表中的所有元素與二分查找一個子表中的所有元素相比。
若在主表中的每個子表後都預留有空閑位置，則索引存儲也便於進行插入和刪除運算，因為其運算過程只涉及到索引表和相應的子表，只需要對相應子表中的元素進行比較和移動，與其它任何子表無關，不像順序表那樣需涉及到整個表中的所有元素，即牽一發而動全身。
在線性表的索引存儲結構上進行插入和刪除運算的演算法，也同查找演算法類似，其過程為：首先根據待插入或刪除元素的某個域(假定子表就是按照此域的值劃分的)的值查找索引表，確定出對應的子表，然後再根據待插入或刪除元素的關鍵字，在該子表中做插入或刪除元素的操作。因為每個子表不是順序存儲，就是鏈接存儲，所以對它們做插入或刪除操作都是很簡單的。

不知道答案與兄台的問題是否一致，也是網上找的，不對請見諒哈~~

Ⅸ 資料庫索引原理

資料庫索引原理如下：

使用索引可快速訪問資料庫表中的特定信息。如果想按特定職員的姓來查找人員，則與在表中搜索所有的行相比，索引有助於更快地獲取信息。

索引的實現通常使用B樹及其變種B+樹。在數據之外，資料庫系統還維護著滿足特定查找演算法的數據結構，這些數據結構以某種方式引用（指向）數據，這樣就可以在這些數據結構上實現高級查找演算法。

(9)索引的實現演算法擴展閱讀：

對於有些列不應該創建索引。一般來說，不應該創建索引的的這些列具有下列特點：

1、查詢很少：

對於那些在查詢中很少使用或者參考的列不應該創建索引。這是因為，既然這些列很少使用到，因此有索引或者無索引，並不能提高查詢速度。相反，由於增加了索引，反而降低了系統的維護速度和增大了空間需求。

2、少數據值：

對於那些只有很少數據值的列也不應該增加索引。這是因為，由於這些列的取值很少，例如人事表的性別列，在查詢的結果中，結果集的數據行佔了表中數據行的很大比例，即需要在表中搜索的數據行的比例很大。增加索引，並不能明顯加快檢索速度。

3、定義類型：

對於那些定義為text, image和bit數據類型的列不應該增加索引。這是因為，這些列的數據量要麼相當大，要麼取值很少。