『壹』 在文件管理中的索引文件中的索引表是放在外存還是內存
原則上來說，資料庫中你建立一個index就會對應一個引索。引索演算法有很多種，如hash,avg-tree等等，去對應不同的需求。 這些引索集合是在資料庫啟動導入內存中的，所以檢索速度很快。外存儲放的是實際的詳細內容。
『貳』 資料庫中索引表本身是存在內存還是外存為什麼有的是內存有的是外存
原則上來說，資料庫中你建立一個index就會對應一個引索。引索演算法有很多種，如hash,avg-tree等等，去對應不同的需求。
這些引索集合是在資料庫啟動導入內存中的，所以檢索速度很快。外存儲放的是實際的詳細內容。
希望你能幫助你。
『叄』 如何寫索引，讓查詢速度快
首先來看看錶是否有索引的命令
show index from 表名；
看到主鍵索引，索引類型是BTREE(二叉樹)
正是因為這個二叉樹演算法，讓查詢速度快很多，二叉樹的原理，就是取最中間的一個數，然後把大於這個數的往右邊排，小於這個數的就向左排，每次減半，然後依次類推，每次減半，形成一個樹狀結構圖
例如上面的例子，我們不使用索引的話，需要查詢11次才把編號為4的數據取出，如果加上索引，我們只需要4次就可以取出。
如大家所知道的，MySQL目前主要有以下幾種索引類型：FULLTEXT，HASH，BTREE，RTREE。
那麼，這幾種索引有什麼功能和性能上的不同呢？
FULLTEXT
即為全文索引，目前只有MyISAM引擎支持。其可以在CREATE TABLE ，ALTER TABLE ，CREATE INDEX 使用，不過目前只有 CHAR、VARCHAR ，TEXT 列上可以創建全文索引。值得一提的是，在數據量較大時候，現將數據放入一個沒有全局索引的表中，然後再用CREATE INDEX創建FULLTEXT索引，要比先為一張表建立FULLTEXT然後再將數據寫入的速度快很多。
全文索引並不是和MyISAM一起誕生的，它的出現是為了解決WHERE name LIKE 「%word%"這類針對文本的模糊查詢效率較低的問題。在沒有全文索引之前，這樣一個查詢語句是要進行遍歷數據表操作的，可見，在數據量較大時是極其的耗時的，如果沒有非同步IO處理，進程將被挾持，很浪費時間，當然這里不對非同步IO作進一步講解，想了解的童鞋，自行谷哥。
全文索引的使用方法並不復雜：
創建ALTER TABLE table ADD INDEX `FULLINDEX` USING FULLTEXT(`cname1`[,cname2…]);
使用SELECT * FROM table WHERE MATCH(cname1[,cname2…]) AGAINST ('word' MODE );
其中， MODE為搜尋方式（IN BOOLEAN MODE ，IN NATURAL LANGUAGE MODE ，IN NATURAL LANGUAGE MODE WITH QUERY EXPANSION / WITH QUERY EXPANSION）。
關於這三種搜尋方式，愚安在這里也不多做交代，簡單地說，就是，布爾模式，允許word里含一些特殊字元用於標記一些具體的要求，如+表示一定要有，-表示一定沒有，*表示通用匹配符，是不是想起了正則，類似吧；自然語言模式，就是簡單的單詞匹配；含表達式的自然語言模式，就是先用自然語言模式處理，對返回的結果，再進行表達式匹配。
對搜索引擎稍微有點了解的同學，肯定知道分詞這個概念，FULLTEXT索引也是按照分詞原理建立索引的。西文中，大部分為字母文字，分詞可以很方便的按照空格進行分割。但很明顯，中文不能按照這種方式進行分詞。那又怎麼辦呢？這個向大家介紹一個Mysql的中文分詞插件Mysqlcft，有了它，就可以對中文進行分詞，想了解的同學請移步Mysqlcft，當然還有其他的分詞插件可以使用。
HASH
Hash這個詞，可以說，自打我們開始碼的那一天起，就開始不停地見到和使用到了。其實，hash就是一種（key=>value）形式的鍵值對，如數學中的函數映射，允許多個key對應相同的value，但不允許一個key對應多個value。正是由於這個特性，hash很適合做索引，為某一列或幾列建立hash索引，就會利用這一列或幾列的值通過一定的演算法計算出一個hash值，對應一行或幾行數據（這里在概念上和函數映射有區別，不要混淆）。在Java語言中，每個類都有自己的hashcode()方法，沒有顯示定義的都繼承自object類，該方法使得每一個對象都是唯一的，在進行對象間equal比較，和序列化傳輸中起到了很重要的作用。hash的生成方法有很多種，足可以保證hash碼的唯一性，例如在MongoDB中，每一個document都有系統為其生成的唯一的objectID（包含時間戳，主機散列值，進程PID，和自增ID）也是一種hash的表現。額，我好像扯遠了-_-!
由於hash索引可以一次定位，不需要像樹形索引那樣逐層查找,因此具有極高的效率。那為什麼還需要其他的樹形索引呢？
在這里愚安就不自己總結了。引用下園子里其他大神的文章：來自 14的路 的MySQL的btree索引和hash索引的區別
（1）Hash 索引僅僅能滿足"=","IN"和"<=>"查詢，不能使用范圍查詢。
由於 Hash 索引比較的是進行 Hash 運算之後的 Hash 值，所以它只能用於等值的過濾，不能用於基於范圍的過濾，因為經過相應的 Hash 演算法處理之後的 Hash 值的大小關系，並不能保證和Hash運算前完全一樣。
（2）Hash 索引無法被用來避免數據的排序操作。
由於 Hash 索引中存放的是經過 Hash 計算之後的 Hash 值，而且Hash值的大小關系並不一定和 Hash 運算前的鍵值完全一樣，所以資料庫無法利用索引的數據來避免任何排序運算；
（3）Hash 索引不能利用部分索引鍵查詢。
對於組合索引，Hash 索引在計算 Hash 值的時候是組合索引鍵合並後再一起計算 Hash 值，而不是單獨計算 Hash 值，所以通過組合索引的前面一個或幾個索引鍵進行查詢的時候，Hash 索引也無法被利用。
（4）Hash 索引在任何時候都不能避免表掃描。
前面已經知道，Hash 索引是將索引鍵通過 Hash 運算之後，將 Hash運算結果的 Hash 值和所對應的行指針信息存放於一個 Hash 表中，由於不同索引鍵存在相同 Hash 值，所以即使取滿足某個 Hash 鍵值的數據的記錄條數，也無法從 Hash 索引中直接完成查詢，還是要通過訪問表中的實際數據進行相應的比較，並得到相應的結果。
（5）Hash 索引遇到大量Hash值相等的情況後性能並不一定就會比B-Tree索引高。
對於選擇性比較低的索引鍵，如果創建 Hash 索引，那麼將會存在大量記錄指針信息存於同一個 Hash 值相關聯。這樣要定位某一條記錄時就會非常麻煩，會浪費多次表數據的訪問，而造成整體性能低下。
愚安我稍作補充，講一下HASH索引的過程，順便解釋下上面的第4,5條：
當我們為某一列或某幾列建立hash索引時（目前就只有MEMORY引擎顯式地支持這種索引），會在硬碟上生成類似如下的文件：
hash值 存儲地址
1db54bc745a1 77#45b5
4bca452157d4 76#4556,77#45cc…
…
hash值即為通過特定演算法由指定列數據計算出來，磁碟地址即為所在數據行存儲在硬碟上的地址（也有可能是其他存儲地址，其實MEMORY會將hash表導入內存）。
這樣，當我們進行WHERE age = 18 時，會將18通過相同的演算法計算出一個hash值==>在hash表中找到對應的儲存地址==>根據存儲地址取得數據。
所以，每次查詢時都要遍歷hash表，直到找到對應的hash值，如（4），數據量大了之後，hash表也會變得龐大起來，性能下降，遍歷耗時增加，如（5）。
BTREE
BTREE索引就是一種將索引值按一定的演算法，存入一個樹形的數據結構中，相信學過數據結構的童鞋都對當初學習二叉樹這種數據結構的經歷記憶猶新，反正愚安我當時為了軟考可是被這玩意兒好好地折騰了一番，不過那次考試好像沒怎麼考這個。如二叉樹一樣，每次查詢都是從樹的入口root開始，依次遍歷node，獲取leaf。
BTREE在MyISAM里的形式和Innodb稍有不同
在 Innodb里，有兩種形態：一是primary key形態，其leaf node里存放的是數據，而且不僅存放了索引鍵的數據，還存放了其他欄位的數據。二是secondary index，其leaf node和普通的BTREE差不多，只是還存放了指向主鍵的信息.
而在MyISAM里，主鍵和其他的並沒有太大區別。不過和Innodb不太一樣的地方是在MyISAM里，leaf node里存放的不是主鍵的信息，而是指向數據文件里的對應數據行的信息.
RTREE
RTREE在mysql很少使用，僅支持geometry數據類型，支持該類型的存儲引擎只有MyISAM、BDb、InnoDb、NDb、Archive幾種。
相對於BTREE，RTREE的優勢在於范圍查找.
各種索引的使用情況
（1）對於BTREE這種Mysql默認的索引類型，具有普遍的適用性
（2）由於FULLTEXT對中文支持不是很好，在沒有插件的情況下，最好不要使用。其實，一些小的博客應用，只需要在數據採集時，為其建立關鍵字列表，通過關鍵字索引，也是一個不錯的方法，至少愚安我是經常這么做的。
（3）對於一些搜索引擎級別的應用來說，FULLTEXT同樣不是一個好的處理方法，Mysql的全文索引建立的文件還是比較大的，而且效率不是很高，即便是使用了中文分詞插件，對中文分詞支持也只是一般。真要碰到這種問題，Apache的Lucene或許是你的選擇。
（4）正是因為hash表在處理較小數據量時具有無可比擬的素的優勢，所以hash索引很適合做緩存（內存資料庫）。如mysql資料庫的內存版本Memsql，使用量很廣泛的緩存工具Mencached，NoSql資料庫redis等，都使用了hash索引這種形式。當然，不想學習這些東西的話Mysql的MEMORY引擎也是可以滿足這種需求的。
『肆』 誰能解釋一下R-tree演算法的意思看不懂！
【轉載】R-Tree空間索引演算法的研究歷程和最新進展分析2008-07-09 23:15摘要：本文介紹了空間索引的概念、R-Tree數據結構和R-Tree空間索引的演算法描述，並從R-Tree索引技術的優缺點對R-Tree的改進結構——變種R-Tree進行了論述。最後，對R-Tree的最新研究進展進行了分析。
關鍵詞：空間索引技術；R-Tree；研究歷程；最新進展
當前數據搜索的一個關鍵問題是速度。提高速度的核心技術是空間索引。空間索引是由空間位置到空間對象的映射關系。當前的一些大型資料庫都有空間索引能力，像Oracle，DB2。
空間索引技術並不單是為了提高顯示速度，顯示速度僅僅是它所要解決的一個問題。空間索引是為空間搜索提供一種合適的數據結構，以提高搜索速度。
空間索引技術的核心是：根據搜索條件，比如一個矩形，迅速找到與該矩形相交的所有空間對象集合。當數據量巨大，矩形框相對於全圖很小時，這個集合相對於全圖數據集大為縮小，在這個縮小的集合上再處理各種復雜的搜索，效率就會大大提高。
所謂空間索引，就是指依據空間實體的位置和形狀或空間實體之間的某種空間關系，按一定順序排列的一種數據結構，其中包含空間實體的概要信息如對象的標識、外接矩形及指向空間實體數據的指針。簡單的說，就是將空間對象按某種空間關系進行劃分，以後對空間對象的存取都基於劃分塊進行。
1 引言
空間索引是對存儲在介質上的數據位置信息的描述，用來提高系統對數據獲取的效率。空間索引的提出是由兩方面決定的：其一是由於計算機的體系結構將存貯器分為內存、外存 兩種，訪問這兩種存儲器一次所花費的時間一般為30~40ns，8~10ms，可以看出兩者相差十 萬倍以上，盡管現在有「內存資料庫」的說法，但絕大多數數據是存儲在外存磁碟上的，如果對磁碟上數據的位置不加以記錄和組織，每查詢一個數據項就要掃描整個數據文件，這種訪問磁碟的代價就會嚴重影響系統的效率，因此系統的設計者必須將數據在磁碟上的位置加以記錄和組織，通過在內存中的一些計算來取代對磁碟漫無目的的訪問，才能提高系統的效率，尤其是GIS涉及的是各種海量的復雜數據，索引對於處理的效率是至關重要的。其二是GIS 所表現的地理數據多維性使得傳統的B樹索引並不適用，因為B樹所針對的字元、數字等傳統數據類型是在一個良序集之中，即都是在一個維度上，集合中任給兩個元素，都可以在這個維度上確定其關系只可能是大於、小於、等於三種，若對多個欄位進行索引，必須指定各個欄位的優先順序形成一個組合欄位，而地理數據的多維性，在任何方向上並不存在優先順序問題，因此B樹並不能對地理數據進行有效的索引，所以需要研究特殊的能適應多維特性的空間索引方式。
1984年Guttman發表了《R樹:一種空間查詢的動態索引結構》，它是一種高度平衡的樹，由中間節點和頁節點組成，實際數據對象的最小外接矩形存儲在頁節點中，中間節點通過聚集其低層節點的外接矩形形成，包含所有這些外接矩形。其後，人們在此基礎上針對不同空間運算提出了不同改進，才形成了一個繁榮的索引樹族，是目前流行的空間索引。
R樹是B樹向多維空間發展的另一種形式，它將空間對象按范圍劃分，每個結點都對應一個區域和一個磁碟頁，非葉結點的磁碟頁中存儲其所有子結點的區域范圍，非葉結點的所有子結點的區域都落在它的區域范圍之內；葉結點的磁碟頁中存儲其區域范圍之內的所有空間對象的外接矩形。每個結點所能擁有的子結點數目有上、下限，下限保證對磁碟空間的有效利用，上限保證每個結點對應一個磁碟頁，當插入新的結點導致某結點要求的空間大於一個磁碟頁時，該結點一分為二。R樹是一種動態索引結構，即：它的查詢可與插入或刪除同時進行，而且不需要定期地對樹結構進行重新組織。
2 R-Tree數據結構
R-Tree是一種空間索引數據結構，下面做簡要介紹：
（1）R-Tree是n 叉樹，n稱為R-Tree的扇（fan）。
（2）每個結點對應一個矩形。
（3）葉子結點上包含了小於等於n 的對象，其對應的矩為所有對象的外包矩形。
（4）非葉結點的矩形為所有子結點矩形的外包矩形。
R-Tree的定義很寬泛，同一套數據構造R-Tree，不同方可以得到差別很大的結構。什麼樣的結構比較優呢？有兩標准：
（1）位置上相鄰的結點盡量在樹中聚集為一個父結點。
（2）同一層中各兄弟結點相交部分比例盡量小。
R樹是一種用於處理多維數據的數據結構，用來訪問二維或者更高維區域對象組成的空間數據.R樹是一棵平衡樹。樹上有兩類結點：葉子結點和非葉子結點。每一個結點由若干個索引項構成。對於葉子結點，索引項形如(Index，Obj_ID)。其中，Index表示包圍空間數據對象的最小外接矩形MBR，Obj_ID標識一個空間數據對象。對於一個非葉子結點，它的索引項形如(Index，Child_Pointer)。 Child_Pointer 指向該結點的子結點。Index仍指一個矩形區域，該矩形區域包圍了子結點上所有索引項MBR的最小矩形區域。一棵R樹的示例如圖所示：
3 R-Tree演算法描述
演算法描述如下：
對象數為n，扇區大小定為fan。
（1）估計葉結點數k=n/fan。
（2）將所有幾何對象按照其矩形外框中心點的x值排序。
（3）將排序後的對象分組，每組大小為 *fan，最後一組可能不滿員。
（4）上述每一分組內按照幾何對象矩形外框中心點的y值排序。
（5）排序後每一分組內再分組，每組大小為fan。
（6）每一小組成為葉結點，葉子結點數為nn。
（7）N=nn，返回1。
4 R-Tree空間索引演算法的研究歷程
1 R-Tree
多維索引技術的歷史可以追溯到20世紀70年代中期。就在那個時候，諸如Cell演算法、四叉樹和k-d樹等各種索引技術紛紛問世，但它們的效果都不盡人意。在GIS和CAD系統對空間索引技術的需求推動下，Guttman於1984年提出了R樹索引結構，發表了《R樹:一種空間查詢的動態索引結構》，它是一種高度平衡的樹，由中間節點和頁節點組成，實際數據對象的最小外接矩形存儲在頁節點中，中間節點通過聚集其低層節點的外接矩形形成，包含所有這些外接矩形。其後，人們在此基礎上針對不同空間運算提出了不同改進，才形成了一個繁榮的索引樹族，是目前流行的空間索引。
2 R+樹
在Guttman的工作的基礎上，許多R樹的變種被開發出來， Sellis等提出了R+樹，R+樹與R樹類似，主要區別在於R+樹中兄弟結點對應的空間區域無重疊，這樣劃分空間消除了R樹因允許結點間的重疊而產生的「死區域」（一個結點內不含本結點數據的空白區域），減少了無效查詢數，從而大大提高空間索引的效率，但對於插入、刪除空間對象的操作，則由於操作要保證空間區域無重疊而效率降低。同時R+樹對跨區域的空間物體的數據的存儲是有冗餘的，而且隨著資料庫中數據的增多，冗餘信息會不斷增長。Greene也提出了他的R樹的變種。
3 R*樹
在1990年，Beckman和Kriegel提出了最佳動態R樹的變種——R*樹。R*樹和R樹一樣允許矩形的重疊，但在構造演算法R*樹不僅考慮了索引空間的「面積」，而且還考慮了索引空間的重疊。該方法對結點的插入、分裂演算法進行了改進，並採用「強制重新插入」的方法使樹的結構得到優化。但R*樹演算法仍然不能有效地降低空間的重疊程度，尤其是在數據量較大、空間維數增加時表現的更為明顯。R*樹無法處理維數高於20的情況。
4 QR樹
QR樹利用四叉樹將空間劃分成一些子空間，在各子空間內使用許多R樹索引，從而改良索引空間的重疊。QR樹結合了四叉樹與R樹的優勢，是二者的綜合應用。實驗證明：與R樹相比，QR樹以略大（有時甚至略小）的空間開銷代價，換取了更高的性能，且索引目標數越多，QR樹的整體性能越好。
5 SS樹
SS樹對R*樹進行了改進，通過以下措施提高了最鄰近查詢的性能：用最小邊界圓代替最小邊界矩形表示區域的形狀，增強了最鄰近查詢的性能，減少將近一半存儲空間；SS樹改進了R*樹的強制重插機制。當維數增加到5是，R樹及其變種中的邊界矩形的重疊將達到90％，因此在高維情況（≥5）下，其性能將變的很差，甚至不如順序掃描。
6 X樹
X樹是線性數組和層狀的R樹的雜合體，通過引入超級結點，大大地減少了最小邊界矩形之間的重疊，提高了查詢效率。X樹用邊界圓進行索引，邊界矩形的直徑（對角線）比邊界圓大，SS樹將點分到小直徑區域。由於區域的直徑對最鄰近查詢性能的影響較大，因此SS樹的最鄰近查詢性能優於R*樹；邊界矩形的平均容積比邊界圓小，R*樹將點分到小容積區域；由於大的容積會產生較多的覆蓋，因此邊界矩形在容積方面要優於邊界圓。SR樹既採用了最小邊界圓（MBS），也採用了最小邊界矩形（MBR），相對於SS樹，減小了區域的面積，提高了區域之間的分離性，相對於R*樹，提高了鄰近查詢的性能。
5 R-Tree空間索引演算法的最新研究
信息的膨脹使資料庫檢索需要面對的問題越來越多。在構建索引方面，最主要面臨的則是如何構造高效的索引演算法來支持各種資料庫系統（比如：多媒體資料庫、空間資料庫等），特別是如何有效的利用演算法來實現加速檢索。概括地說，R-Tree空間索引演算法的研究要做到：支持高維數據空間；有效分割數據空間，來適應索引的組織；高效的實現多種查詢方式系統中的統一。R-Tree的索引結構最新研究不能是單純為了加速某種查詢方式或提高某個方面的性能，忽略其他方面的效果，這樣可能會造成更多不必要的性能消耗。
XML作為可擴展的標示語言，其索引方法就是基於傳統的R-Tree索引技術的XR-Tree索引方法。該方法構造了適合於XML數據的索引結構。XR-Tree索引方法是一種動態擴充內存的索引數據結構，針對XISS（XML Indexing and Storage System：XML索引和存儲體系）中結構連接中的問題，設計了基於XR-Tree索引樹有效地跳過不參與匹配的元素的連接演算法。但這種索引方法在進行路徑的連接運算中仍然存儲大量的中間匹配結果，為此一種基於整體查詢模式的基於索引的路徑連接演算法提出，即利用堆棧鏈表來臨時壓棧存儲產生的部分匹配結果，並且隨著匹配的動態進行出棧操作。這樣在查詢連接處理完成以後，直接輸出最終結果，既節省了存儲空間又提高了操作效率。
『伍』 資料庫索引的實現原理
資料庫索引的實現原理
一、概述資料庫索引，是資料庫管理系統中一個排序的數據結構，以協助快速查詢、更新資料庫表中數據。索引的實現通常使用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 索引有哪些各⽤用了了哪些數據結構
從數據結構角度
1、B+樹索引(O(log(n)))：關於B+樹索引，可以參考 MySQL索引背後的數據結構及演算法原理
2、hash索引：
a 僅僅能滿足"=","IN"和"<=>"查詢，不能使用范圍查詢
b 其檢索效率非常高，索引的檢索可以一次定位，不像B-Tree 索引需要從根節點到枝節點，最後才能訪問到頁節點這樣多次的IO訪問，所以 Hash 索引的查詢效率要遠高於 B-Tree 索引
c 只有Memory存儲引擎顯示支持hash索引
3、FULLTEXT索引（現在MyISAM和InnoDB引擎都支持了）
4、R-Tree索引（用於對GIS數據類型創建SPATIAL索引）
『柒』 談談資料庫索引 用自己話說
資料庫原索引不僅表現在排序和查找上,更主要的是通過建立合適的索引,還可以防止關鍵字重復!建立索引的資料庫和沒有建立索引的資料庫在查找速度上,不是一倍兩倍的問題,而是幾何級倍的問題!所以,不管是什麼資料庫,至少要建立一個索引.很簡的道理,你要在網上搜一個主題,如果你要搜的主題在資料庫中不是索引欄位,那查找是非常耗時的.但如果你有建立相應的索引,那結果就是天壤之別!
『捌』 什麼是基於索引搜索 動態分配演算法
倒排索引表中的每一項都包括一個屬性值和具有該屬性值的各記錄的地址。由於不是由記錄來確定屬性值，而是由屬性值來確定記錄的位置，因而稱為倒排索引(inverted index)。帶有倒排索引的文件我們稱為倒排索引文件，簡稱倒排文件。建立全文索引中有兩項非常重要，一個是如何對文本進行分詞，一是建立索引的數據結構。分詞的方法基本上是二元分詞法、最大匹配法和統計方法。索引的數據結構基本上採用倒排索引的結構。
分詞的好壞關繫到查詢的准確程度和生成的索引的大小。在中文分詞發展中，早期經常使用分詞方式是二元分詞法，該方法的基本原理是將包含中文的句子進行二元分割，不考慮單詞含義，只對二元單詞進行索引。因此該方法所分出的單詞數量較多，從而產生的索引數量巨大，查詢中會將無用的數據檢索出來，好處是演算法簡單不會漏掉檢索的數據。之後又發展出最大匹配分詞方法，該方法又分為正向最大分詞和逆向最大分詞。其原理和查字典類似，對常用單詞生成一個詞典，分析句子的過程中最大的匹配字典中的單詞，從而將句子拆分為有意義的單詞鏈。最大匹配法中正向分詞方法對偏正式詞語的分辨容易產生錯誤，比如「首飾和服裝」會將「和服」作為單詞分出。達夢資料庫採用的是改進的逆向最大分詞方法，該分詞方法較正向正確率有所提高。最為復雜的是通過統計方式進行分詞的方法。該方法採用隱式馬爾科夫鏈，也就是後一個單詞出現的概率依靠於前一個單詞出現的概率，最後統計所有單詞出現的概率的最大為分詞的依據。這個方法對新名詞和地名的識別要遠遠高於最大匹配法，准確度隨著取樣文本的數量的增大而提高。
二元分詞方法和統計方法是不依賴於詞典的，而最大匹配法分詞方法是依賴於詞典的，詞典的內容決定分詞結構的好壞。
全文檢索的索引被稱為倒排索引，之所以成為倒排索引，是因為將每一個單詞作為索引項，根據該索引項查找包含該單詞的文本。因此，索引都是單詞和唯一記錄文本的標示是一對多的關系。將索引單詞排序，根據排序後的單詞定位包含該單詞的文本。
步驟1）讀取一整條句子到變數str中，轉到步驟2
步驟2）從句子的尾端讀取1個字到變數word中，轉到步驟3
步驟3）在字典查找word中保存的單詞。如果存在則保存word，轉到步驟4，否則轉到步驟5）
步驟4）如果是字典中最大單詞或者超過最大單詞數（認定為新詞），從句尾去掉該單詞，返回步驟2
步驟5）讀取前一個字到word中，構成新單詞，轉到步驟3）
詞庫的內存數據結構和詞庫中單詞的匹配演算法
內存中單詞採用層次結構保存
『玖』 索引順序查找演算法
索引查找是在索引表和主表(即線性表的索引存儲結構)上進行的查找。索引查找的過程是：首先根據給定的索引值K1，在索引表上查找出索引值等於KI的索引項，以確定對應予表在主表中的開始位置和長度，然後再根據給定的關鍵字K2，茬對應的子表中查找出關鍵字等於K2的元素(結點)。對索引表或子表進行查找時，若表是順序存儲的有序表，則既可進行順序查找，也可進行二分查找，否則只能進行順序查找。
設數組A是具有mainlist類型的一個主表，數組B是具有inde)dist類型的在主表A 上建立的一個索引表，m為索引表B的實際長度，即所含的索引項的個數，KI和K2分別為給定待查找的索引值和關鍵字(當然它們的類型應分別為索引表中索引值域的類型和主表中關鍵字域在索引存儲中，不僅便於查找單個元素，而且更便於查找一個子表中的全部元素。當需要對一個子袁中的全部元素依次處理時，只要從索引表中查找出該子表的開始位置即可。由此開始位置可以依次取出該子表中的每一個元素，所以整個查找過程的時間復雜度為，若不是採用索引存儲，而是採用順序存儲，即使把它組織成有序表而進行二分查找時，索引查找一個子表中的所有元素與二分查找一個子表中的所有元素相比。
若在主表中的每個子表後都預留有空閑位置，則索引存儲也便於進行插入和刪除運算，因為其運算過程只涉及到索引表和相應的子表，只需要對相應子表中的元素進行比較和移動，與其它任何子表無關，不像順序表那樣需涉及到整個表中的所有元素，即牽一發而動全身。
在線性表的索引存儲結構上進行插入和刪除運算的演算法，也同查找演算法類似，其過程為：首先根據待插入或刪除元素的某個域(假定子表就是按照此域的值劃分的)的值查找索引表，確定出對應的子表，然後再根據待插入或刪除元素的關鍵字，在該子表中做插入或刪除元素的操作。因為每個子表不是順序存儲，就是鏈接存儲，所以對它們做插入或刪除操作都是很簡單的。
不知道答案與兄台的問題是否一致，也是網上找的，不對請見諒哈~~
『拾』 C語言中什麼是索引
1.索引表的類型可定義如下：
struct IndexItem
{
IndexKeyType index;
//IndexKeyType為事先定義的索引值類型
int start;
//子表中第一個元素所在的下標位置
int length;
//子表的長度域
};
2.首先根據給定的索引值K1，在索引表上查找出索引值等於K1的索引項，以確定對應子表在主表中的開始位置和長度，然後再根據給定的關鍵字K2，在對應的子表中查找出
3。關鍵字等於K2的元素。
設數組A是具有mainlist類型的一個主表，數組B是具有indexlist類型的在主表A上建立的一個索引表，m為索引表B的實際長度，即所含的索引項的個數，K1和K2分別為給定
帶查找的索引值和關鍵字，並假定每個子表採用順序存儲，則索引查找演算法為：
int Indsch(mainlist A, indexlist B, int m, IndexKeyType K1, KeyType K2)
{//利用主表A和大小為 m 的索引表B索引查找索引值為K1，關鍵字為K2的記錄
//返回該記錄在主表中的下標位置，若查找失敗則返回-1
int i, j;
for (i = 0; i < m; i++)
if (K1 == B[i].index)
break;
if (i == m)
return -1; //查找失敗
j = B[i].start;
while (j < B[i].start + B[i].length)
{
if (K2 == A[j].key)
break;
else
j++;
}
if (j < B[i].start + B[i].length)
return j; //查找成功
else
return -1; //查找失敗
}