索引

• 為什么要使用索引

  要考慮這個問題，首先要從最基礎(chǔ)的查找表中數(shù)據(jù)的過程開始說起。通常我們在查找一個序列中的某一個元素時，用到的最簡單的方式就是遍歷，數(shù)據(jù)庫也是一樣，在一張表中查找某一行數(shù)據(jù)時，如果不考慮索引的狀況下，也會采用一個逐行掃描的方式，只不過數(shù)據(jù)庫通常以塊或者頁為單位，所以它通常將整個塊或者頁加載進(jìn)內(nèi)存，然后逐塊輪詢查找到結(jié)果并返回。如果數(shù)據(jù)庫中只有少量數(shù)據(jù)，那么進(jìn)行全表掃描，速度還是會很快，但是如果在數(shù)據(jù)量很大的表中，這種方法就不再適用了，在數(shù)據(jù)量很大的表中，由于逐行掃描代價變大，通常需要避免采用這種逐行掃描的方式進(jìn)行數(shù)據(jù)查找，數(shù)據(jù)庫為了使查詢變得高效，所以引入了索引這種方式對數(shù)據(jù)進(jìn)行查找。

• 什么樣的信息能成為索引

  1.主鍵、唯一鍵、普通鍵

• 索引的數(shù)據(jù)結(jié)構(gòu)

  • 二叉查找樹

    眾所周知，二叉查找樹是每個節(jié)點最多由兩個子樹的樹結(jié)構(gòu)，而其還有一個特點是，在任意一顆樹中，根節(jié)點的左孩子永遠(yuǎn)小于根節(jié)點，根節(jié)點的右孩子永遠(yuǎn)大于根節(jié)點，用二叉查找樹作為索引，確實可以提高查找效率，其可以使用二分查找將時間復(fù)雜度控制在O(lgn)，但是二叉查找樹有一個顯而易見的缺陷，當(dāng)某種特殊情況（按照某個特定順序插入樹）發(fā)生時，二叉查找樹將變?yōu)橄聢D右側(cè)（線性二叉樹）的狀況：

    此時二叉查找樹查找任意某個元素時，其查找順序與逐行查找無異，查詢時間復(fù)雜度又將回到O(n)，查詢效率無法保持。

  • B-Tree

    B-Tree，平衡多路查找樹，如果每個節(jié)點，最多有N個孩子，那么這樣的樹就叫N階B-Tree， 每個節(jié)點中主要包含關(guān)鍵字和指向孩子的指針，最多能有幾個孩子，取決于節(jié)點的容量和數(shù)據(jù)庫的相關(guān)配置，通常情況下這個N是很大的。
    B-Tree作為一種數(shù)據(jù)結(jié)構(gòu)，有如下特征：
    1.根節(jié)點至少包含兩個孩子
    2.樹中每個節(jié)點至多含有N個孩子（N>=2)
    3.除根節(jié)點和葉節(jié)點外，其它每個節(jié)點至少有ceil(N/2)個孩子。（ceil表示取上限，例如1.2的上限為2，1.1的上限也為2，非四舍五入）
    4.所有葉子節(jié)點都位于同一層，即葉子節(jié)點的高度都是一樣的。
    5.假設(shè)每個非終端節(jié)點包含n個關(guān)鍵字信息（P0,P1...Pn,k1...kn）
    

    ( a )ki(i=1..n)為關(guān)鍵字，且關(guān)鍵字按順序升序排序k(i-1)<ki。
    ( b )關(guān)鍵字的個數(shù)必須滿足：[ceil(m/2)-1]<=n<=m-1]。
    ( c )非葉子節(jié)點的指針：P[1],P[2]...P[M];其中P[1]指向關(guān)鍵字小于K[1]的子樹，P[N]指向關(guān)鍵字大于K[N-1]的子樹，其它P[i]指向關(guān)鍵字屬于(K[i-1],K[i])的子樹。
    

    遵守上述規(guī)則，其目的就是盡量使每個索引塊都盡可能多的存儲數(shù)據(jù)，盡可能減少查找次數(shù)以提升效率。 舉個例子，模擬一下查找過程，以便于理解：假設(shè)我們要查詢關(guān)鍵字為10的數(shù)據(jù)，則從根節(jié)點出發(fā)，10<17，于是通過P1進(jìn)入其孩子節(jié)點，10>8且10<12，于是通過P2進(jìn)入其孩子節(jié)點，最后尋找到10。如果不使用索引，而使用逐行掃描的方式進(jìn)行查找，則從0開始至少掃描10次才能查找到10號數(shù)據(jù)，有了索引之后可以看到，查找次數(shù)從10變?yōu)?，大大提高了查找效率。
    如果這里是二叉查找樹，會出現(xiàn)極端情況，使得查找時間復(fù)雜度為O(n),而如果是B-Tree，由于上述五個約束，可以讓節(jié)點通過合并、分裂、上移、下移等操作，使得樹高度較二叉查找樹小，查找效率顯然更高。

  • B+ -Tree（MySQL）

    B+ -Tree是B-Tree的一個變體，其定義基本與B樹相同，除了:
    1.非葉子節(jié)點的子樹指針與關(guān)鍵字個數(shù)相同，其表明B+樹能存儲更多的關(guān)鍵字
    2.非葉子節(jié)點的子樹指針P[i]，指向關(guān)鍵字值[K[i],K[i+1])的子樹。
    3.非葉子節(jié)點僅用來做索引，數(shù)據(jù)到保存在葉子節(jié)點中。（B+樹的所有檢索都是從根部開始，直到搜索到葉子節(jié)點結(jié)束。）
    4.所有葉子節(jié)點均有一個鏈指針，指向下一個葉子節(jié)點。（方便直接在葉子節(jié)點直接做范圍統(tǒng)計）
    

    B+樹相較于B樹的優(yōu)勢：
    1.B+樹的磁盤讀寫代價更低。
    2.B+樹的查詢效率更加穩(wěn)定。
    3.B+樹更有利于對數(shù)據(jù)庫的掃描。
    

  • Hash

    Hash索引是根據(jù)Hash結(jié)構(gòu)的定義，只需要一次運(yùn)算便可以找到數(shù)據(jù)所在位置，不像B+樹或者B樹需要從根結(jié)點出發(fā)尋找數(shù)據(jù)，所以Hash索引的查詢效率理論上要高于B+樹索引，但是MySQL中并沒有采用這一種索引，這是由于這種索引除查詢效率之外的缺陷是十分明顯的。
    1.僅僅只能滿足"=","IN",不能使用范圍查詢。由于其是由Hash運(yùn)算獲取的數(shù)據(jù)存放位置，每次Hash運(yùn)算獲取的是一個確定的值，且這個值并不與數(shù)據(jù)本身的大小有關(guān)系，所以其并不能滿足范圍查詢。
    2.無法被用來避免數(shù)據(jù)的排序操作。和1的意思差不多，Hash的索引值是由Hash運(yùn)算獲取的，其索引值與數(shù)據(jù)本身的大小并無明顯關(guān)系。
    3.不能利用部分索引鍵查詢。
    4.不能避免表掃描。由于Hash索引會產(chǎn)生Hash沖突，存在Hash沖突的數(shù)據(jù)會被連接到同一個鏈表上，當(dāng)大量數(shù)據(jù)被連接到相同鏈表上時，查詢某條數(shù)據(jù)就變成了掃描該鏈表，時間復(fù)雜度并不能保證在O(1)。
    5.遇到大量Hash值相等的情況后性能并不一定就會比B-Tree索引高。
    

  • BitMap索引

    位圖索引，當(dāng)表中的某個字段只有幾種值的時候，例如：性別，此時用位圖索引是一個最佳的選擇。目前使用位圖索引的比較主流的數(shù)據(jù)庫有Oracle數(shù)據(jù)庫。

• 密集索引和稀疏索引的區(qū)別

  1.密集索引文件中的每個搜索碼都對應(yīng)一個索引值，稀疏索引文件只為索引碼的某些值建立索引項。
  2.密集索引將數(shù)據(jù)存儲與索引放到了一塊，找到索引也就找到了數(shù)據(jù)，稀疏索引將數(shù)據(jù)和索引分開存儲，索引結(jié)構(gòu)的葉子節(jié)點指向數(shù)據(jù)的對應(yīng)行。
  

  • 關(guān)于MySQL的MyISAM和InnoDB
    MyISAM不論是主鍵索引、唯一鍵索引、還是普通索引，都采用的是稀疏索引，而InnoDB必須有且僅有一個密集索引。
    InnoDB密集索引規(guī)則：
    1.若一個主鍵被定義，該主鍵則作為密集索引。
    2.若沒有主鍵被定義，該表的第一個唯一非空索引則作為密集索引。
    3.若不滿足以上條件，InnoDB內(nèi)部會生成一個隱藏主鍵（密集索引）。
    4.非主鍵索引存儲相關(guān)鍵位和其對應(yīng)的主鍵值，包含兩次查找。
    注：InnoDB如果查詢條件為主鍵索引，則只需查詢一次，但是輔助索引需要查詢兩次，先通過輔助索引查詢到主鍵索引，再查詢到數(shù)據(jù)。
    從上圖中可以看到，如果一個索引是聚集索引，則其葉子節(jié)點上存放的即是數(shù)據(jù)本身，而如果一個索引是稀疏索引，葉子節(jié)點存放的僅是地址，指向?qū)⒁檎业臄?shù)據(jù)。

• 如何定位并優(yōu)化慢查詢SQL

  首先先建立一張表

  CREATE DATABASE sqltest; use sqltest; create table tb_test(test_id int primary key auto_increment,test_name varchar(1024),test_date datetime,test_desc varchar(1024) );

總結(jié)

以上是生活随笔為你收集整理的[转载] --- 数据库基本知识的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。