摘要：為了減少查找這些記錄的開銷，我們可以為存儲數據庫的文件創建索引。理想情況下，系統應該能夠直接定位這些記錄，為了實現這種訪問數據的方式，設計出了附加結構并將其與數據庫的文件關聯起來，這種附加結構被稱為索引。

　　本文大部分內容來自數據庫系統概念(Data System Concepts)一書以及mooc上數據庫系統戰德臣老師的課程，這里只是自己加上自己的一些思考總結下筆記

　　建立數據庫索引的原因：當對于數據庫的許多查詢只涉及文件中很少一部分記錄時。為了減少查找這些記錄的開銷，我們可以為存儲數據庫的文件創建索引。
　　例如:類似于“找出Perryridge分支機構的所有賬戶信息”或者“找出賬號為A-101的余額”的查詢，這種查詢只涉及所有賬戶記錄中的一小部分，如果系統讀取所有的記錄并一一檢查branch_name字段值為“Perryridge”的記錄，或者檢查account_number字段找出值為“A-101”的記錄，這樣的操作方式是低效的。理想情況下，系統應該能夠直接定位這些記錄，為了實現這種訪問數據的方式，設計出了附加結構并將其與數據庫的文件關聯起來，這種附加結構被稱為“索引”。
　　索引的分類有兩種：順序索引和散列索引，順序索引是基于值的有序序列，散列索引是基于將值均勻分布在若干個散列桶當中，一個值所示的散列桶是由一個函數決定的，該函數被稱為散列函數。
　　評價不同的索引技術的指標主要有：訪問類型(找到具有特定屬性值的所有記錄與在某個特定范圍的所有記錄)、訪問時間(找到一個特定數據項或者數據項集)、插入時間(找到插入的正確位置的時間+更新索引結構的時間)、刪除時間(找到待刪除數據項位置的時間+更新索引結構的時間)、空間開銷(索引結構額外占用的存儲空間)。
　　搜索碼：用于在文件中查找記錄的屬性或屬性集。如果在一個文件有多個索引，那么它就有多個搜索碼。

　　聚集索引或主索引：包含記錄的文件內部是按照某個搜索碼指定的順序對所包含記錄進行排序的(即11.7中的順序文件組織)，那么該搜索碼對應的索引稱為聚集索引。也被稱為主索引，但這里的主索引并不是單指建立在主碼上的索引，而是可以建立在任何前面條件的搜索碼上，雖然通常是主碼。
　　非聚集索引或輔助索引：搜索碼指定的順序與文件中的記錄的物理順序不同的索引。
　　索引項或者索引記錄：由一個搜索碼值和指向該搜索碼值的一個或者多個記錄的指針構成。指向記錄的指針包括磁盤塊的標識和記錄在標識磁盤塊內的塊內偏移量

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

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

　　輔助索引即非聚集索引必須是稠密索引，為了避免稠密索引出現重復值，可以采取指針桶的辦法，將對應同一個搜索碼值的記錄的指針都放到同一個指針桶當中，再用搜索碼值對應的索引項指向這個指針桶

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

　　B+樹的查詢插入刪除更新操作原理結合可視化數據結構

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

procedure insert(value K,point P)
    找到應該包含值K的葉節點L
    if(L所含搜索碼少于n-1個)
            then insertInLeaf(L,K,P)
    else begin //L已經含有n-1個搜索碼了，分裂L
        創建結點L"
        把L.P1,...,L.Kn-1復制到可以存儲n個(指針,搜索碼)對的內存塊T//注意這里是n對所以能把K也放進去了
        insertInLeaf(T,K,P)
        令L".Pn=L.Pn;令L.Pn=L"http://原來的L變成了L+L"
        把T.P1,...,T.K?n/2?從T復制到L中，以L.P1作為開始
        把T.P?n/2?+1,...,T.Kn從T復制到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是樹的根節點//通過父指針是不是null來判斷
        then begin
            創建新結點R包含N、K"、N" //N和N"都是指針
            令R成為樹的根節點
            return
        end
    令P=parent(N)
    if(P包含的指針少于n個)
        then 將(K",N")插到P中N后面
    else begin //分裂P
        將P復制到可以存放P以及(K",N")的內存塊T中
        把結點(K",N")插入T當中，緊跟在N后面
        刪除P中所有項；創建結點P"
        把T.P1,...,T.P?n/2?復制到P
        令K""=T.K?n/2?
        把T.P?n/2?+1,...,T.Kn復制到P"
        //所有的指針都保留下來了，搜索碼值僅有兩節點的分割點T.K?n/2?未保留，但是傳到父結點當中了
        insertInParent(P,K"",P")
    end

偽代碼待補充

?

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

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

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

扇區、塊/簇、page的關系：

扇區： 硬盤的最小讀寫單元

塊/簇： 是操作系統針對硬盤讀寫的最小單元

page： 是內存與操作系統之間操作的最小單元。

扇區 <= 塊/簇 <= 頁
　　我們都知道計算機在存儲數據的時候，有最小存儲單元，這就好比我們今天進行現金的流通最小單位是一毛。在計算機中磁盤存儲數據最小單元是扇區，一個扇區的大小是512字節，而文件系統（例如XFS/EXT4）他的最小單元是塊，一個塊的大小是4k，而對于我們的InnoDB存儲引擎也有自己的最小儲存單元——頁（Page），一個頁的大小是16K。

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

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