索引
為什么我們需要索引
加快數(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è)置索引,以獲取最大的收益圆恤。