資料庫查找演算法

『壹』 如何查看資料庫的演算法

資料庫裡面最常用的排序演算法莫過於合並排序。
優化的查找演算法如二分查找、二叉樹查找等，雖然查找效率提高了。但是各自對檢索的數據都有要求：二分查找要求被檢索數據有序，而二叉樹查找只能應用於二叉查找樹上，但是數據本身的組織結構不可能完全滿足各種數據結構。
資料庫查詢是資料庫的主要功能之一，最基本的查詢演算法是順序查找時間復雜度為O(n)，顯然在數據量很大時效率很低。優化的查找演算法如二分查找、二叉樹查找等，雖然查找效率提高了。

『貳』 資料庫select使用什麼演算法，比如查詢以m開頭的字元串

第一步：應用程序把查詢SQL語句發給伺服器端執行

我們在數據層執行SQL語句時，應用程序會連接到相應的資料庫伺服器，把SQL語句發送給伺服器處理。

第二步：伺服器解析請求的SQL語句

1.SQL計劃緩存，經常用查詢分析器的朋友大概都知道這樣一個事實，往往一個查詢語句在第一次運行的時候需要執行特別長的時間，但是如果你馬上或者在一定時間內運行同樣的語句，會在很短的時間內返回查詢結果。

原因：

• 伺服器在接收到查詢請求後，並不會馬上去資料庫查詢，而是在資料庫中的計劃緩存中找是否有相對應的執行計劃，如果存在，就直接調用已經編譯好的執行計劃，節省了執行計劃的編譯時間。

• 如果所查詢的行已經存在於數據緩沖存儲區中，就不用查詢物理文件了，而是從緩存中取數據，這樣從內存中取數據就會比從硬碟上讀取數據快很多，提高了查詢效率.數據緩沖存儲區會在後面提到。

2.如果在SQL計劃緩存中沒有對應的執行計劃，伺服器首先會對用戶請求的SQL語句進行語法效驗，如果有語法錯誤，伺服器會結束查詢操作，並用返回相應的錯誤信息給調用它的應用程序。

注意:此時返回的錯誤信息中，只會包含基本的語法錯誤信息，例如select寫成selec等，錯誤信息中如果包含一列表中本沒有的列，此時伺服器是不會檢查出來的，因為只是語法驗證，語義是否正確放在下一步進行。

3.語法符合後，就開始驗證它的語義是否正確，例如，表名，列名，存儲過程等等資料庫對象是否真正存在，如果發現有不存在的，就會報錯給應用程序，同時結束查詢。

4.接下來就是獲得對象的解析鎖，我們在查詢一個表時，首先伺服器會對這個對象加鎖，這是為了保證數據的統一性，如果不加鎖，此時有數據插入，但因為沒有加鎖的原因，查詢已經將這條記錄讀入，而有的插入會因為事務的失敗會回滾，就會形成臟讀的現象。

5.接下來就是對資料庫用戶許可權的驗證，SQL語句語法，語義都正確，此時並不一定能夠得到查詢結果，如果資料庫用戶沒有相應的訪問許可權，伺服器會報出許可權不足的錯誤給應用程序，在稍大的項目中，往往一個項目裡面會包含好幾個資料庫連接串，這些資料庫用戶具有不同的許可權，有的是只讀許可權，有的是只寫許可權，有的是可讀可寫，根據不同的操作選取不同的用戶來執行，稍微不注意，無論你的SQL語句寫的多麼完善，完美無缺都沒用。

6.解析的最後一步，就是確定最終的執行計劃。當語法，語義，許可權都驗證後，伺服器並不會馬上給你返回結果，而是會針對你的SQL進行優化，選擇不同的查詢演算法以最高效的形式返回給應用程序。例如在做表聯合查詢時，伺服器會根據開銷成本來最終決定採用hashjoin，mergejoin，還是loopjoin，採用哪一個索引會更高效等等，不過它的自動化優化是有限的，要想寫出高效的查詢SQL還是要優化自己的SQL查詢語句。

當確定好執行計劃後，就會把這個執行計劃保存到SQL計劃緩存中，下次在有相同的執行請求時，就直接從計劃緩存中取，避免重新編譯執行計劃。

第三步：語句執行

伺服器對SQL語句解析完成後，伺服器才會知道這條語句到底代表了什麼意思，接下來才會真正的執行SQL語句。

這時分兩種情況:

• 如果查詢語句所包含的數據行已經讀取到數據緩沖存儲區的話，伺服器會直接從數據緩沖存儲區中讀取數據返回給應用程序，避免了從物理文件中讀取，提高查詢速度。

• 如果數據行沒有在數據緩沖存儲區中，則會從物理文件中讀取記錄返回給應用程序，同時把數據行寫入數據緩沖存儲區中，供下次使用。

說明:SQL緩存分好幾種，這里有興趣的朋友可以去搜索一下，有時因為緩存的存在，使得我們很難馬上看出優化的結果，因為第二次執行因為有緩存的存在，會特別快速，所以一般都是先消除緩存，然後比較優化前後的性能表現，這里有幾個常用的方法:

DBCCDROPCLEANBUFFERS

從緩沖池中刪除所有清除緩沖區。

DBCCFREEPROCCACHE

從過程緩存中刪除所有元素。

DBCCFREESYSTEMCACHE

從所有緩存中釋放所有未使用的緩存條目。SQLServer2005資料庫引擎會事先在後台清理未使用的緩存條目，以使內存可用於當前條目。但是，可以使用此命令從所有緩存中手動刪除未使用的條目。

這只能基本消除SQL緩存的影響，目前好像沒有完全消除緩存的方案，如果大家有，請指教。

結論:只有知道了服務執行應用程序提交的SQL的操作流程才能很好的調試我們的應用程序。

• 確保SQL語法正確;

• 確保SQL語義上的正確性，即對象是否存在;

• 資料庫用戶是否具有相應的訪問許可權。

『叄』 數據的演算法都有哪些……

A*搜尋演算法
俗稱A星演算法。這是一種在圖形平面上，有多個節點的路徑，求出最低通過成本的演算法。常用於游戲中的 NPC的移動計算，或線上游戲的 BOT的移動計算上。該演算法像 Dijkstra演算法一樣，可以找到一條最短路徑；也像BFS一樣，進行啟發式的搜索。

Beam Search
束搜索(beam search)方法是解決優化問題的一種啟發式方法，它是在分枝定界方法基礎上發展起來的，它使用啟發式方法估計k個最好的路徑，僅從這k個路徑出發向下搜索，即每一層只有滿意的結點會被保留，其它的結點則被永久拋棄，從而比分枝定界法能大大節省運行時間。束搜索於20 世紀70年代中期首先被應用於 人工智慧領域,1976 年Lowerre在其稱為 HARPY的語音識別系統中第一次使用了束搜索方法。他的目標是並行地搜索幾個潛在的最優決策路徑以減少回溯，並快速地獲得一個解。

二分取中查找演算法
一種在有序數組中查找某一特定元素的搜索演算法。搜素過程從數組的中間元素開始，如果中間元素正好是要查找的元素，則搜素過程結束；如果某一特定元素大於或者小於中間元素，則在數組大於或小於中間元素的那一半中查找，而且跟開始一樣從中間元素開始比較。這種搜索演算法每一次比較都使搜索范圍縮小一半。

Branch and bound
分支定界演算法是一種在問題的解空間樹上搜索問題的解的方法。但與回溯演算法不同，分支定界演算法採用廣度優先或最小耗費優先的方法搜索解空間樹，並且，在分支定界演算法中，每一個活結點只有一次機會成為擴展結點。

數據壓縮
數據壓縮是通過減少計算機中所存儲數據或者通信傳播中數據的冗餘度，達到增大數據密度，最終使數據的存儲空間減少的技術。數據壓縮在文件存儲和分布式系統領域有著十分廣泛的應用。數據壓縮也代表著尺寸媒介容量的增大和網路帶寬的擴展。

Diffie–Hellman密鑰協商
Diffie–Hellman key exchange，簡稱「D–H」，是一種安全協議。它可以讓雙方在完全沒有對方任何預先信息的條件下通過不安全信道建立起一個密鑰。這個密鑰可以在後續的通訊中作為對稱密鑰來加密通訊內容。

Dijkstra』s 演算法
迪科斯徹演算法（Dijkstra）是由荷蘭計算機科學家艾茲格·迪科斯徹發明的。演算法解決的是有向圖中單個源點到其他頂點的最短路徑問題。舉例來說，如果圖中的頂點表示城市，而邊上的權重表示著城市間開車行經的距離，迪科斯徹演算法可以用來找到兩個城市之間的最短路徑。

動態規劃
動態規劃是一種在 數學和計算機科學中使用的，用於求解包含重疊子問題的最優化問題的方法。其基本思想是，將原問題分解為相似的子問題，在求解的過程中通過子問題的解求出原問題的解。 動態規劃的思想是多種演算法的基礎，被廣泛應用於計算機科學和工程領域。比較著名的應用實例有：求解最短路徑問題，背包問題，項目管理，網路流優化等。這里也有一篇文章說得比較詳細。

歐幾里得演算法
在 數學中，輾轉相除法，又稱 歐幾里得演算法，是求 最大公約數的演算法。輾轉相除法首次出現於 歐幾里得的《幾何原本》（第VII卷，命題i和ii）中，而在中國則可以追溯至 東漢出現的《九章算術》。

快速傅里葉變換(FFT)
快速傅里葉變換（Fast Fourier Transform，FFT），是離散傅里葉變換的快速演算法，也可用於計算離散傅里葉變換的逆變換。快速傅里葉變換有廣泛的應用，如數字信號處理、計算大整數乘法、求解偏微分方程等等。

哈希函數
HashFunction是一種從任何一種數據中創建小的數字「指紋」的方法。該 函數將數據打亂混合，重新創建一個叫做散列值的指紋。散列值通常用來代表一個短的隨機字母和數字組成的字元串。好的散列 函數在輸入域中很少出現散列沖突。在散列表和數據處理中，不抑制沖突來區別數據，會使得資料庫記錄更難找到。

堆排序
Heapsort是指利用堆積樹（堆）這種 數據結構所設計的一種排序演算法。堆積樹是一個近似完全二叉樹的結構，並同時滿足堆積屬性：即子結點的鍵值或索引總是小於（或者大於）它的父結點。

歸並排序
Merge sort是建立在歸並操作上的一種有效的排序演算法。該演算法是採用分治法（Divide and Conquer）的一個非常典型的應用。

RANSAC 演算法
RANSAC 是」RANdom SAmpleConsensus」的縮寫。該演算法是用於從一組觀測數據中估計 數學模型參數的迭代方法，由Fischler and Bolles在1981提出，它是一種非確定性演算法，因為它只能以一定的概率得到合理的結果，隨著迭代次數的增加，這種概率是增加的。該演算法的基本假設是觀測數據集中存在」inliers」（那些對模型參數估計起到支持作用的點）和」outliers」（不符合模型的點），並且這組觀測數據受到雜訊影響。RANSAC 假設給定一組」inliers」數據就能夠得到最優的符合這組點的模型。

RSA加密演演算法
這是一個公鑰加密演算法，也是世界上第一個適合用來做簽名的演算法。今天的RSA已經 專利失效，其被廣泛地用於 電子商務加密，大家都相信，只要密鑰足夠長，這個演算法就會是安全的。

並查集Union-find
並查集是一種樹型的 數據結構，用於處理一些不相交集合（Disjoint Sets）的合並及查詢問題。常常在使用中以森林來表示。

Viterbi algorithm
尋找最可能的隱藏狀態序列
等等這些，演算法很多。

『肆』 hash查找演算法 數據量在10萬左右 資料庫中存儲

可以用，但是最好加入緩存機制。

『伍』 多媒體資料庫中的常用的查詢與檢索方法是什麼

由特徵分析子系統、特徵提取子系統、資料庫、查詢介面、檢索引擎和索引過濾等子系統組成，同時需要相應的知識輔助支持特定領域的內容處理。

（1）特徵分析：該子系統負責將需要入庫的媒體進行分割或節段化，標識出需要的對象或內容關鍵點，以便有針對性的對目標進行特徵提取。特徵標識可通過用戶輸入或系統定義。

（2）特徵提取對用戶提供或系統標明的媒體對象進行特徵提取處理。提取特徵時需要知識處理模塊的輔助，與標准化的知識定義直接有關。

（3）資料庫包含多媒體資料庫和特徵資料庫，分別存放多媒體數據同對應的特徵數據，它們彼此之間存在著一定的對應關系。特徵庫中包含了由用戶輸入的和預處理自動提取的特徵數據，通過檢索引擎組織與媒體類型相匹配的索引來達到快速搜索的目的。

（4）查詢介面，即人機交互界面，友好的人機交互界面是檢索系統不可缺少的。在基於內容的檢索中，由於特徵不直觀，因此必須為用戶提供一個可視化的輸入手段，還應在用戶界面提供查詢結果的創覽功能，即為用戶提供初步查詢結果的返回，系統會根據用戶選擇的排序標准(如顏色、旋律、節拍等)，按照相似度的大小將結果排列後，返回給用戶。

（5）檢索引擎，檢索要將特徵提取值和特徵庫中的值進行比較，得到一個相似度。不同的媒體各自具有不同的相似度演算法，這些演算法也稱為相似性測度函數。檢索引擎使用相似性測度函數集去進行比較，從而確定與特徵庫的值最接近的多媒體數據。

（6）索引過濾在大規模多媒體數據檢索過程中，為了提高檢索效率，常在檢索引擎進行匹配之前採用索引過濾方法，取出高維特徵用於匹配。

『陸』 資料庫索引的實現原理

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

『柒』 資料庫得查詢功能是怎麼實現的

資料庫的查詢功能實現原理：

資料庫查詢是資料庫的最主要功能之一。我們都希望查詢數據的速度能盡可能的快，因此資料庫系統的設計者會從查詢演算法的角度進行優化。最基本的查詢演算法當然是順序查找（linear search），這種復雜度為O(n)的演算法在數據量很大時顯然是糟糕的，好在計算機科學的發展提供了很多更優秀的查找演算法，例如二分查找（binary search）、二叉樹查找（binary tree search）等。如果稍微分析一下會發現，每種查找演算法都只能應用於特定的數據結構之上，例如二分查找要求被檢索數據有序，而二叉樹查找只能應用於二叉查找樹上，但是數據本身的組織結構不可能完全滿足各種數據結構（例如，理論上不可能同時將兩列都按順序進行組織），所以，在數據之外，資料庫系統還維護著滿足特定查找演算法的數據結構，這些數據結構以某種方式引用（指向）數據，這樣就可以在這些數據結構上實現高級查找演算法。這種數據結構，就是索引。

圖1展示了一種可能的索引方式。左邊是數據表，一共有兩列七條記錄，最左邊的是數據記錄的物理地址（注意邏輯上相鄰的記錄在磁碟上也並不是一定物理相鄰的）。為了加快Col2的查找，可以維護一個右邊所示的二叉查找樹，每個節點分別包含索引鍵值和一個指向對應數據記錄物理地址的指針，這樣就可以運用二叉查找在O(log2n)O(log2n)的復雜度內獲取到相應數據。

『捌』 資料庫索引原理

資料庫索引原理如下：

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

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

(8)資料庫查找演算法擴展閱讀：

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

1、查詢很少：

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

2、少數據值：

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

3、定義類型：

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