54、資料庫索引
索引的優缺點
優點：
1、大大加快資料的檢索速度；
2、建立唯一性索引，保證資料庫表中每一行資料的唯一性；
3、加速表和表之間的連接配接；
4、在使用分組和排序子句進行資料檢索時，可以顯著減少查詢中分組和排序的時間。
缺點：
1、索引需要占實體空間；
2、當對表中的資料進行增加、删除和修改的時候，索引也要動态的維護，降低資料的維護速度。
索引的分類
1、唯一索引： 是在表上一個或者多個字段組合建立的索引，這個或者這些字段的值組合起來在表中不可以重複。
2、非唯一索引： 是在表上一個或者多個字段組合建立的索引，這個或者這些字段的值組合起來在表中可以重複，不要求唯一。
3、主鍵索引（主索引）： 是唯一索引的特定類型。表中建立主鍵時自動建立的索引，一個表隻能建立一個主索引。
4、聚集索引（聚簇索引、Innodb）：表中記錄的實體順序與鍵值的索引順序相同。 因為真實資料的實體順序隻有一種，是以一個表隻能有一個聚集索引。葉子節點（B+樹）存儲真實的資料行，不再有另外單獨的資料頁。
5、非聚集索引（Mylsam）：表中記錄的實體順序與鍵值的索引順序不同。這也是非聚集索引與聚集索引的根本差別。葉子節點并非資料節點，而是每一個指向真正資料行的指針。
聚集索引與非聚集索引的差別：
1）、聚集索引的優缺點：優點是查詢速度快，因為一旦具有第一個索引值的記錄被找到，具有連續索引值的記錄也一定實體的緊跟其後。缺點是對表進行修改速度較慢，這是為了保持表中的記錄的實體順序與索引順序的一緻，而把記錄插入到資料頁的相應位置，必須在資料頁中進行資料重排，降低了執行速度。在插入新記錄時資料檔案為了維持 B+Tree 的特性而頻繁的分裂調整，十分低效。
建議使用聚集索引的場合為：A.某列包含了小數目的不同值。B.排序和範圍查找。
2）、聚集索引和非聚集索引都采用了B+樹的結構，但非聚集索引的葉子層并不與實際的資料頁相重疊，而采用葉子層包含一個指向表中的記錄在資料頁中的指針的方式。聚集索引的葉節點就是資料節點，而非聚集索引的葉節點仍然是索引節點。
3）、非聚集索引添加記錄時，不會引起資料順序的重組。
看上去聚簇索引的效率明顯要低于非聚簇索引，因為每次使用輔助索引檢索都要經過兩次 B+樹查找，這不是多此一舉嗎？聚簇索引的優勢在哪？
1)、由于行資料和葉子節點存儲在一起，這樣主鍵和行資料是一起被載入記憶體的，找到葉子節點就可以立刻将行資料傳回了，如果按照主鍵 Id 來組織資料，獲得資料更快。
2)、輔助索引使用主鍵作為"指針"，而不是使用位址值作為指針的好處是，減少了當出現行移動或者資料頁分裂時，輔助索引的維護工作，InnoDB 在移動行時無須更新輔助索引中的這個"指針"。也就是說行的位置會随着資料庫裡資料的修改而發生變化，使用聚簇鍵索引就可以保證不管這個主鍵 B+ 樹的節點如何變化，輔助索引樹都不受影響。
6、組合索引： 基于多個字段而建立的索引就稱為組合索引，組合索引的使用要遵從最左字首。在最左字首原則中，範圍查詢會導緻組合索引半生效，where子句有or出現還是會周遊全表。
Mysql怎麼增加一個索引
建立索引：create index idx1 on table(col1, col2, col3);
添加索引：alter table tablename add index indexname(col1, col2);
55、資料庫索引的實作
目前大部分資料庫系統及檔案系統都采用B-Tree（B樹）或其變種B+Tree（B+樹）作為索引結構。B+Tree 是資料庫系統實作索引的首選資料結構。
在 MySQL 中，索引屬于存儲引擎級别的概念， 不同存儲引擎對索引的實作方式是不同的。
MyISAM 索引實作（非聚集索引）
MyISAM引擎使用B+Tree作為索引結構，葉節點的data域存放的是資料記錄的位址。
圖8是一個MyISAM表的主索引（Primary Key）示意，可以看出 MyISAM 的索引檔案僅僅儲存資料記錄的位址。在 MyISAM 中，主索引和輔助索引（Secondary key）在結構上沒有任何差別，隻是主索引要求 key 是唯一的，而輔助索引的 key 可以重複。如果我們在 Col2 上建立一個輔助索引，則此索引的結構如下圖所示：
同樣也是一顆 B+Tree，data 域儲存資料記錄的位址。是以，MyISAM 中索引檢索的算法會首先按照 B+Tree 搜尋算法搜尋索引，如果指定的 Key 存在，則取出其data 域的值，然後以 data 域的值為位址，讀取相應資料記錄。
InnoDB 索引實作（聚集索引）
MyISAM 索引檔案和資料檔案是分離的，索引檔案僅儲存資料記錄的位址。而在InnoDB 中，表資料檔案本身就是按 B+Tree 組織的一個索引結構，這棵樹的葉節點data 域儲存了完整的資料記錄（第一個重大差別）。 這個索引的 key 是資料表的主鍵，是以 InnoDB 表資料檔案本身就是主索引。
上圖是 InnoDB 主索引（同時也是資料檔案）的示意圖，可以看到葉節點包含了完整的資料記錄。這種索引叫做聚集索引。因為 InnoDB 的資料檔案本身要按主鍵聚集。
1、InnoDB 要求表必須有主鍵（MyISAM 可以沒有）， 如果沒有顯式指定，則 MySQL系統會自動選擇一個可以唯一辨別資料記錄的列作為主鍵，如果不存在這種列，則MySQL 自動為 InnoDB 表生成一個隐含字段作為主鍵，類型為長整形。
2、盡量在 InnoDB 上采用自增字段做表的主鍵。 因為 InnoDB 資料檔案本身是一棵B+Tree，非單調的主鍵會造成在插入新記錄時資料檔案為了維持 B+Tree 的特性而頻繁的分裂調整，十分低效，而使用自增字段作為主鍵則是一個很好的選擇。如果表使用自增主鍵，那麼每次插入新的記錄，記錄就會順序添加到目前索引節點的後續位置，當一頁寫滿，就會自動開辟一個新的頁。
這樣就會形成一個緊湊的索引結構，近似順序填滿。由于每次插入時也不需要移動已有資料，是以效率很高，也不會增加很多開銷在維護索引上。
第二個與 MyISAM 索引的不同是 InnoDB 的輔助索引 data 域存儲相應記錄主鍵的值而不是位址。 換句話說，InnoDB 的所有輔助索引都引用主鍵作為 data 域。
聚集索引這種實作方式使得按主鍵的搜尋十分高效，但是輔助索引搜尋需要檢索兩遍索引：首先檢索輔助索引獲得主鍵，然後用主鍵到主索引中檢索獲得記錄。
引申：為什麼不建議使用過長的字段作為主鍵？因為所有輔助索引都引用主索引，過長的主索引會令輔助索引變得過大。
總結
InnoDB使用的是聚簇索引，将主鍵組織到一棵 B+樹中，而行資料就儲存在葉子節點上，若使用"where id = 14"這樣的條件查找主鍵，則按照 B+樹的檢索算法即可查找到對應的葉節點，之後獲得行資料。若對 Name 列進行條件搜尋，則需要兩個步驟：第一步在輔助索引 B+樹中檢索 Name，到達其葉子節點擷取對應的主鍵。第二步使用主鍵在主索引B+樹中再執行一次 B+樹檢索操作，最終到達葉子節點即可擷取整行資料。
MyISAM 使用的是非聚簇索引，非聚簇索引的兩棵 B+樹看上去沒什麼不同，節點的結構完全一緻隻是存儲的内容不同而已，主鍵索引 B+樹的節點存儲了主鍵，輔助鍵索引B+樹存儲了輔助鍵。表資料存儲在獨立的地方，這兩顆 B+樹的葉子節點都使用一個位址指向真正的表資料，對于表資料來說，這兩個鍵沒有任何差别。由于索引樹是獨立的，通過輔助鍵檢索無需通路主鍵的索引樹。
56、為什麼使用B+樹作為索引
B/B+ 樹性能分析
1、n 個節點的平衡二叉樹的高度為 H(即 logn)，而 n 個節點的 B/B+樹的高度為logt((n+1)/2)+1；
2、若要作為記憶體中的查找表，B 樹卻不一定比平衡二叉樹好，尤其當 m 較大時更是如此。因為查找操作 CPU 的時間在 B-樹上是 O(mlogtn)=O(lgn(m/lgt))，而 m/lgt>1；是以 m較大時O(mlogtn)比平衡二叉樹的操作時間大得多。是以在記憶體中使用B樹必須取較小的m。（通常取最小值 m=3，此時 B-樹中每個内部結點可以有 2 或 3 個孩子，這種 3 階的 B-樹稱為 2-3 樹）。
為什麼說 B+tree比 B 樹更适合實際應用中作業系統的檔案索引和資料索引。
B+tree 的内部節點并沒有指向關鍵字具體資訊的指針，是以其内部節點相對 B 樹更小， 如果把所有同一内部節點的關鍵字存放在同一盤塊中，那麼盤塊所能容納的關鍵字數量也越多，一次性讀入記憶體的需要查找的關鍵字也就越多，相對 IO 讀寫次數就降低了。
由于非終結點并不是最終指向檔案内容的結點，而隻是葉子結點中關鍵字的索引。是以任何關鍵字的查找必須走一條從根結點到葉子結點的路。所有關鍵字查詢的路徑長度相同，導緻每一個資料的查詢效率相當。
也有人認為資料庫索引采用 B+樹的主要原因是：B 樹在提高了 IO 性能的同時并沒有解決元素周遊的效率低下的問題，正是為了解決這個問題，B+樹應用而生。B+樹隻需要去周遊葉子節點就可以實作整棵樹的周遊。而且在資料庫中基于範圍的查詢是非常頻繁的，而 B樹不支援這樣的操作（或者說效率太低，需要中序周遊）。