索引
為什么我們需要索引
加快數(shù)據(jù)庫的查詢速度佃声。
實現(xiàn)
索引的基本原理：保存一些元數(shù)據(jù)作為路標函似，幫助我們快速查找數(shù)據(jù)咒唆。如果我們想要以不同的方式查找同一份數(shù)據(jù)镶殷，可能需要建立多份索引聪全。
哈希：單行查詢的時間復雜度是 O(1)，但是范圍查詢的時間復雜度會退化到 O(n)载佳，而 SQL 有很多范圍查詢炒事。
-
樹：平衡樹的增刪查改的時間復雜度是 O(lg(n))，與樹的高度成正比蔫慧。但是挠乳，不同平衡樹的區(qū)別是對磁盤IO的優(yōu)化。
- 平衡二叉搜索樹：（1）樹的高度比較高姑躲，一次查詢可能比較慢睡扬。（2）一個節(jié)點只存儲了一條記錄，需要多次磁盤IO黍析。
- B 樹：（1）m 叉樹存儲大量數(shù)據(jù)時卖怜，樹的高度仍然比較低。（2）一個節(jié)點存儲了多條記錄橄仍，如果將一個節(jié)點的大小設(shè)置為磁盤頁大小韧涨，例如 4K，可充分利用磁盤預讀的特性侮繁，極大地減少磁盤 IO 次數(shù)虑粥。
- B+ 樹：將葉子節(jié)點組成了一個有序鏈表，范圍查詢的效率比 B 樹高宪哩。
優(yōu)缺點
優(yōu)點：大大加快查找數(shù)據(jù)的速度娩贷。
缺點：維護索引會產(chǎn)生額外的開銷，特別是寫入的時候锁孟。任何類型的索引都會減慢寫入速度彬祖，因為每次寫操作都會更新索引。所以品抽，數(shù)據(jù)庫通常不會為所有數(shù)據(jù)生成索引储笑，需要程序員或DBA基于應用查詢模式的了解來正確設(shè)置索引，以獲取最大的收益圆恤。
