聚集索引或主索引：包含記錄的文件內(nèi)部是按照某個(gè)搜索碼指定的順序?qū)λ涗涍M(jìn)行排序的(即11.7中的順序文件組織)，那么該搜索碼對(duì)應(yīng)的索引稱為聚集索引。也被稱為主索引，但這里的主索引并不是單指建立在主碼上的索引，而是可以建立在任何前面條件的搜索碼上，雖然通常是主碼。
　　非聚集索引或輔助索引：搜索碼指定的順序與文件中的記錄的物理順序不同的索引。
　　索引項(xiàng)或者索引記錄：由一個(gè)搜索碼值和指向該搜索碼值的一個(gè)或者多個(gè)記錄的指針構(gòu)成。指向記錄的指針包括磁盤塊的標(biāo)識(shí)和記錄在標(biāo)識(shí)磁盤塊內(nèi)的塊內(nèi)偏移量

　　稠密索引：文件中的每一個(gè)搜索碼值有一個(gè)索引記錄，稠密索引可能是聚集的也可能是非聚集的。這里的搜索碼值可以有重復(fù)的，但對(duì)于聚集索引而言，在實(shí)現(xiàn)上沒有必要是重復(fù)的，指向具有該搜索碼值的第一個(gè)數(shù)據(jù)記錄即可。
　　稀疏索引：只為搜索碼的某些值建立索引記錄，稀疏索引只能是聚集的。與聚集稠密索引一樣，每個(gè)索引記錄也包括了一個(gè)搜索碼值和一個(gè)指向具有該搜索碼值的第一個(gè)數(shù)據(jù)記錄的指針。為了定位一條記錄，我們找到其最大搜索碼值和指向具有該搜索碼值的第一個(gè)數(shù)據(jù)記錄的指針。為了定位一條記錄我們找到小于等于所找記錄搜索碼值的最大搜索碼值對(duì)應(yīng)的索引項(xiàng)，然后從該索引項(xiàng)的指向的記錄開始，沿著文件中的指針查找，直到找到所需的記錄為止。
　　稀疏索引與稠密索引的比較：通常利用稠密索引可以比稀疏索引更快地定位一條記錄。但是稀疏索引也有比稠密索引優(yōu)越的地方：所占空間小，并且插入和刪除時(shí)的維護(hù)開銷也較小。系統(tǒng)設(shè)計(jì)者必須在存取時(shí)間和空間開銷之間進(jìn)行權(quán)衡，但是為每個(gè)塊建一個(gè)索引項(xiàng)是一個(gè)較好的折中，原因在于，處理數(shù)據(jù)庫(kù)請(qǐng)求的開銷主要由把塊從磁盤中讀入到主存當(dāng)中的時(shí)間決定。一旦將塊放入主存，掃描整個(gè)塊的時(shí)間是可以忽略的(對(duì)應(yīng)于稀疏索引從索引項(xiàng)指向的記錄開始，沿著文件中的指針查找，直到找到所需的記錄的時(shí)間是可以忽略的)。使用這樣的稀疏索引，可以定位包含我們要查找的記錄的塊。這樣，只要記錄不在溢出塊(11.7.1)，就能使塊訪問次數(shù)最小，同時(shí)能保持索引盡可能的小(因而減少了空間開銷)。

　　多級(jí)索引(建立在成塊稀疏索引之上的)：當(dāng)數(shù)據(jù)量比較大時(shí)，索引本身即使是采取了(成塊)稀疏索引也還是會(huì)變得非常大難以有效處理。
　　如對(duì)于一個(gè)10w條記錄的文件，假設(shè)一個(gè)磁盤塊能存儲(chǔ)10條記錄，如果每個(gè)塊有一個(gè)索引記錄那么索引就有1w條記錄。索引記錄比數(shù)據(jù)記錄小，假設(shè)一個(gè)磁盤塊能容納100條索引記錄。這樣，索引將占據(jù)100個(gè)磁盤塊。這樣大的索引如在主存中放不下那么就必須以順序文件的方式存儲(chǔ)在磁盤上。這樣即使在索引文件上使用二分查找來定位索引項(xiàng)，搜索的開銷依然很大(如索引占據(jù)b個(gè)磁盤塊，二分搜索需要讀取log2b(向上取整)次)，對(duì)于有100塊的索引，二分查找需要7次讀索引塊操作(這里指的是最壞情況下50+25+12+6+3+1+2)。如果使用了溢出塊那么就不能使用二分查找，而是使用的順序搜索，最壞情況下需要b次。
　　為了解決這種對(duì)于大量記錄下讀塊次數(shù)過多的問題，出現(xiàn)了多級(jí)索引，即在成塊的稀疏索引(內(nèi)層索引)上再建立稀疏索引，被稱為外層索引。比如還上面那個(gè)例子，為了我們已經(jīng)建立100個(gè)索引塊(1w條索引項(xiàng))來指向所有記錄所在塊(1w塊)，那再建立一個(gè)針對(duì)這100個(gè)索引塊的外層成塊稀疏索引，很明顯只要1個(gè)索引塊就夠了，這一個(gè)索引塊能夠放到內(nèi)存當(dāng)中。這樣的話我們就只需要1次讀索引塊(根據(jù)外層索引塊所確定的那個(gè)內(nèi)層索引塊)的操作就能找到特定記錄所在的磁盤塊了。如果外層索引塊依然是太大不能放到主存當(dāng)中，那就繼續(xù)對(duì)其建立上級(jí)索引，直到最外層索引能夠放到主存當(dāng)中。
　　無論采用何種形式的索引，每當(dāng)文件中有記錄插入或者刪除時(shí)，索引都需要更新。系統(tǒng)根據(jù)索引時(shí)稠密索引還是稀疏索引而進(jìn)行下一個(gè)操作。更新的算法具體看書上P321頁(yè)。

　　輔助索引即非聚集索引必須是稠密索引，為了避免稠密索引出現(xiàn)重復(fù)值，可以采取指針桶的辦法，將對(duì)應(yīng)同一個(gè)搜索碼值的記錄的指針都放到同一個(gè)指針桶當(dāng)中，再用搜索碼值對(duì)應(yīng)的索引項(xiàng)指向這個(gè)指針桶

　　索引順序文件組織的最大缺點(diǎn)在于，隨著文件的增大，索引查找性能和數(shù)據(jù)順序掃描性能都會(huì)下降這里講的是單級(jí)的索引順序文件，缺點(diǎn):1.在介紹多級(jí)索引時(shí)也說了需要的IO次數(shù)是與索引磁盤塊成對(duì)數(shù)關(guān)系的，這里的解決方法就是采取多級(jí)索引，B+樹就是一種多級(jí)索引；2.并且對(duì)于出現(xiàn)在溢出塊當(dāng)中的還必須順序查找就更慢了，這里的嚴(yán)格地說是存放記錄的文件組織方式即順序文件組織造成的，因?yàn)楫?dāng)塊滿了的時(shí)候，它會(huì)將記錄放到溢出塊中，就不能使用順序查找了。這個(gè)問題的解決就是用到了后面講到的B+樹文件組織方式，雖然這種性能下降可以通過對(duì)文件進(jìn)行重新組織來彌補(bǔ)，但是我們不希望頻繁地進(jìn)行重組。這里彌補(bǔ)的是第二點(diǎn)，把溢出塊中的記錄整理回排序塊了，避免了出現(xiàn)順序查找。書上說的是有溢出塊出現(xiàn)不能使用二分查找了，個(gè)人理解是在還是可以的，找到對(duì)應(yīng)記錄塊中然后通過指針就能繼續(xù)找到溢出塊中的記錄了，只不過是還要再多IO一次把對(duì)應(yīng)的溢出塊加載進(jìn)來然后找到，還是沒太弄清楚教材上為什么說只能順序查找。

　　B+樹的查詢插入刪除更新操作原理結(jié)合可視化數(shù)據(jù)結(jié)構(gòu)

procedure find(value V)
    設(shè)置C=根節(jié)點(diǎn)
    while C不是葉節(jié)點(diǎn) begin
        找到大于V的最小搜索碼值Ki(如果有的話)
        if 沒有這樣的值 then begain
            令m=結(jié)點(diǎn)中指針的數(shù)目
            設(shè)置C=Pm指向的結(jié)點(diǎn)
        end
        else 設(shè)置C=Pi指向的結(jié)點(diǎn)
    end
    if C中有一個(gè)碼值Ki,滿足Ki=V
        then 指針Pi指向我們需要的記錄或指針桶
        else 不存在具有碼值為k的記錄

procedure insert(value K,point P)
    找到應(yīng)該包含值K的葉節(jié)點(diǎn)L
    if(L所含搜索碼少于n-1個(gè))
            then insertInLeaf(L,K,P)
    else begin //L已經(jīng)含有n-1個(gè)搜索碼了，分裂L
        創(chuàng)建結(jié)點(diǎn)L"
        把L.P1,...,L.Kn-1復(fù)制到可以存儲(chǔ)n個(gè)(指針,搜索碼)對(duì)的內(nèi)存塊T//注意這里是n對(duì)所以能把K也放進(jìn)去了
        insertInLeaf(T,K,P)
        令L".Pn=L.Pn;令L.Pn=L"http://原來的L變成了L+L"
        把T.P1,...,T.K?n/2?從T復(fù)制到L中，以L.P1作為開始
        把T.P?n/2?+1,...,T.Kn從T復(fù)制到L"中，以L".P1作為開始
        令K"表示L"中最小搜索碼值insertInParent
        insertInParent(L,K",L")
    end
procedure insertInLeaf(node L,vlaue K,pointer P)
    if K比L.K1小
        then 把P,K插入到L中，緊接L.P1前面
    else begin
        令Ki表示L中小于K的最大搜索碼值
        把P,K插入L中,緊接T.Ki后面
    end
        
procedure insertInParent(node N,vlaue K",node N")
    if N是樹的根節(jié)點(diǎn)//通過父指針是不是null來判斷
        then begin
            創(chuàng)建新結(jié)點(diǎn)R包含N、K"、N" //N和N"都是指針
            令R成為樹的根節(jié)點(diǎn)
            return
        end
    令P=parent(N)
    if(P包含的指針少于n個(gè))
        then 將(K",N")插到P中N后面
    else begin //分裂P
        將P復(fù)制到可以存放P以及(K",N")的內(nèi)存塊T中
        把結(jié)點(diǎn)(K",N")插入T當(dāng)中，緊跟在N后面
        刪除P中所有項(xiàng)；創(chuàng)建結(jié)點(diǎn)P"
        把T.P1,...,T.P?n/2?復(fù)制到P
        令K""=T.K?n/2?
        把T.P?n/2?+1,...,T.Kn復(fù)制到P"
        //所有的指針都保留下來了，搜索碼值僅有兩節(jié)點(diǎn)的分割點(diǎn)T.K?n/2?未保留，但是傳到父結(jié)點(diǎn)當(dāng)中了
        insertInParent(P,K"",P")
    end

偽代碼待補(bǔ)充

?

　　教材和PPT上在起初介紹都是將葉子節(jié)點(diǎn)中存放的是搜索碼值和搜索碼值對(duì)應(yīng)記錄的指針，但在Mysql當(dāng)中(其他數(shù)據(jù)庫(kù)還未確定，但這種應(yīng)該是使適用的)葉子節(jié)點(diǎn)存放的直接就是對(duì)應(yīng)的記錄了(按聚簇索引搜索碼排序)，并不需要再弄個(gè)指針去指向記錄所在的位置)。

　　但這點(diǎn)其實(shí)教材數(shù)據(jù)庫(kù)系統(tǒng)概念在P330上也有說，這種用來解決存儲(chǔ)實(shí)際記錄的性能下降問題(溢出塊造成)，即在樹中葉子節(jié)點(diǎn)存儲(chǔ)實(shí)際記錄而不是指向記錄的指針的方式就被稱為B+樹文件組織。

　　注意B+樹索引或B+樹文件組織中，樹中相鄰的葉節(jié)點(diǎn)可能分布在磁盤中的不同位置。當(dāng)一個(gè)文件組織最初在建立一組記錄上的傷害，可以把磁盤上基本連續(xù)的塊分配給樹中連續(xù)的葉節(jié)點(diǎn)(這樣就不光邏輯上是連續(xù)的，物理上也是連續(xù)的，比如多個(gè)磁盤塊或者磁盤頁(yè)可能就在一個(gè)磁道上，減少了尋道時(shí)間)。由此，對(duì)葉節(jié)點(diǎn)的順序掃描也就幾乎是順序的掃描。隨著樹中不斷進(jìn)行插入和刪除操作，這種順序性逐漸丟失，對(duì)葉節(jié)點(diǎn)的順序訪問也僅只是邏輯上連續(xù)，在物理存儲(chǔ)上也需要越來越頻繁地等待磁盤尋道。為了恢復(fù)這種物理連續(xù)性，也許需要對(duì)索引進(jìn)行重建。具體可看索引重建(重組)的常見問題。

扇區(qū)、塊/簇、page的關(guān)系：

扇區(qū)： 硬盤的最小讀寫單元

塊/簇： 是操作系統(tǒng)針對(duì)硬盤讀寫的最小單元

page： 是內(nèi)存與操作系統(tǒng)之間操作的最小單元。

扇區(qū) <= 塊/簇 <= 頁(yè)
　　我們都知道計(jì)算機(jī)在存儲(chǔ)數(shù)據(jù)的時(shí)候，有最小存儲(chǔ)單元，這就好比我們今天進(jìn)行現(xiàn)金的流通最小單位是一毛。在計(jì)算機(jī)中磁盤存儲(chǔ)數(shù)據(jù)最小單元是扇區(qū)，一個(gè)扇區(qū)的大小是512字節(jié)，而文件系統(tǒng)（例如XFS/EXT4）他的最小單元是塊，一個(gè)塊的大小是4k，而對(duì)于我們的InnoDB存儲(chǔ)引擎也有自己的最小儲(chǔ)存單元——頁(yè)（Page），一個(gè)頁(yè)的大小是16K。

　　看到了關(guān)于MySQL當(dāng)?shù)闹芯奂饕c二級(jí)索引的術(shù)語(yǔ)說法，查了半天各種博客也沒說出來這個(gè)二級(jí)索引到底是個(gè)什么東西？后面找到了官方頁(yè)面的解釋才算清楚Clustered and Secondary Indexes。ps：其實(shí)二級(jí)索引就是非聚集索引(輔助索引)，聚簇索引就是聚集索引。
　　聚簇索引在Mysql中指的是對(duì)于每一張表有且僅有一個(gè)索引，當(dāng)在建表的時(shí)候定義了主鍵的時(shí)候，那么InnoDB就是將這個(gè)主鍵作為聚簇索引的搜索碼來生成索引，如果未定義主鍵但表中有唯一鍵并且唯一鍵值當(dāng)中沒有null存在的話就把這個(gè)唯一鍵作為聚簇索引的搜索碼(或者叫關(guān)鍵字、索引鍵等等)，如果連這樣一個(gè)唯一鍵都還找不到的話，那么InnoDB則會(huì)隱式的給你根據(jù)6字節(jié)大小行ID作為搜索碼來生成一個(gè)聚簇索引，這個(gè)行ID是你在插入記錄的時(shí)候InnoDB自動(dòng)遞增地給賦的值。聚簇索引也就是數(shù)據(jù)庫(kù)系統(tǒng)概念上的聚集索引，選擇了什么字段作為搜索碼，那么在InnoDB表數(shù)據(jù)文件都是基于這個(gè)搜索碼進(jìn)行順序組織的。也就是說對(duì)于采用行ID作為搜索碼而言的聚簇索引，其表中的記錄的物理存儲(chǔ)就是按照插入順序排序的。這樣的聚簇索引是采用B+樹來實(shí)現(xiàn)的
　　在MySql當(dāng)中建立索引是基于上面的那個(gè)聚簇索引的，即在輔助索引的非葉子結(jié)點(diǎn)那一層所包含的是按輔助索引搜索碼排好序的一個(gè)個(gè)索引塊，里面除了有輔助索引的搜索碼值外還有搜索碼值對(duì)應(yīng)的該表的聚簇索引的搜索碼值，這樣我們也能通過B+樹來實(shí)現(xiàn)了輔助索引，但我們最后得到并不再直接是對(duì)應(yīng)的記錄了，而是一個(gè)表的聚簇索引的搜索碼值，再根據(jù)這個(gè)搜索碼值去聚簇索引的B+樹當(dāng)中去找到對(duì)應(yīng)的記錄即可。所以一般說主鍵不要設(shè)置的的太長(zhǎng)，因?yàn)橐坏┙⒘溯o助索引所有主鍵都復(fù)制一份的，主鍵過長(zhǎng)就會(huì)導(dǎo)致占用空間較多，當(dāng)有多個(gè)輔助索引時(shí)情況更嚴(yán)重。關(guān)于IO次數(shù)，這樣算下來是兩次B+樹查詢IO次數(shù)也不過是2倍的樹高，在Mysql中一般就是2-6而已。
　　至于為什么輔助索引當(dāng)中不直接存放指向記錄的指針呢，原因可以參看由淺入深理解索引的實(shí)現(xiàn)或者教材P334頁(yè)12.5.5輔助索引和記錄重定位：一些文件組織如B+樹文件組織可能改變記錄的位置，Mysql聚簇索引采用的正是B+樹 ，即使記錄并沒有更新。舉例來說，當(dāng)B+樹文件組織中的一個(gè)磁盤頁(yè)被分裂，一些記錄會(huì)被移到新的磁盤頁(yè)。在這種情況下，所有存儲(chǔ)了定向重定位的記錄的指針的輔助索引必須更新，即使記錄中的值并沒有改變。每個(gè)磁盤頁(yè)可能包含相當(dāng)多的記錄，而其中每個(gè)記錄度可能被分配到每個(gè)輔助索引上的不同位置，。因此一次葉磁盤頁(yè)的分裂可能需要幾十甚至幾百次IO操作來更新所有影響到的輔助索引，導(dǎo)致這個(gè)操作代價(jià)及其高昂，為了解決這個(gè)問題，采用的方法就是在輔助索引當(dāng)中，我們不存儲(chǔ)指向索引記錄的指針，而是存儲(chǔ)主索引(聚簇索引)的搜索碼屬性的值。

　　InnoDB一棵B+樹可以存放多少行數(shù)據(jù)？這篇文章以InnoDB中的三層B+樹能放多少行數(shù)據(jù)做出了詳細(xì)清楚的解答。其實(shí)就是先根據(jù)聚簇索引搜索碼字段長(zhǎng)度Lm、指向磁盤頁(yè)的指針長(zhǎng)度Lp(默認(rèn)6B)、磁盤頁(yè)的大小L(默認(rèn)16K)根據(jù)(n-1)Lm+nLp<=L得出最大的n,那么就最多能指向n^2葉節(jié)點(diǎn)個(gè)磁盤頁(yè)，再根據(jù)一條記錄大小Lr,根據(jù)mLr<=L算出最大的m，就得出了最大的記錄數(shù)mn^2