索引是什么?為什么要使用索引??
以前學數據結構時學了ArrayList,我們可以往里面存放數據
但是有問題,也就是說當程序重啟或是電腦關機之后,數據就沒有了,為什么?
因為他的數據是保存在內存中的
數據庫把數據保存在磁盤中,就可以完成對數據的持久化
內存與外存的區別 內存：容量小造價高速度快，斷電后數據丟失 外存：容量大造價低速度慢斷電后數據不丟失,只要寫入就是永久保存索引是一種特殊的文件,包含著對數據表里所有記錄的引用指針。可以對表中的一列或多列創建索引，并指定索引的類型,各類索引有各自的數據結構實現。
索引作用：
數據庫中的表、數據、索引之間的關系,類似于書架上的圖書、書籍內容和書籍目錄的關系。
索引所起的作用類似書籍目錄,可用于快速定位、檢索數據。
索引對于提高數據庫的性能有很大的幫助。MySQL的索引是一種數據結構,它可以幫助數據庫高效地查詢、更新數據表中的數據。索引通過一定的規則排列數據表中的記錄,使得對表的查詢可以通過對索引的搜索來加快速度。
不同的數據結構都有自己實現的規則,不同的規則導致不同數據結構的效率不同
最終時間復雜度和空間復雜度不同2.2為什么要使用索引? MySQL實現的兩個關鍵目標,安全,效率 顯而易見,使用索引的目的只有一個,就是提升數據檢索的效率,在應用程序的運行過程中,查 詢操作的頻率遠遠高于增刪改的頻率。
索引應該選擇哪種數據結構
?1.HASH
時間復雜度是0(1),查詢速度非常快,但是MySQL并沒有選擇HASH做為索引的默認數據結
構,主要原因是HASH不支持范圍查找2.二叉搜索樹
中序遍歷是一個有序序列-->支持范圍查找
時間復雜度:可能會退化成一個單邊樹O(N)
節點個數過多時,無法保證樹的高度
由于數據庫中的數據是在磁盤上保存的,每一次訪問子節點都會發生一次磁盤IO
磁盤IO是制約數據庫性能的主要因素3.N叉樹
每個節點可以有超過兩個的子節點,可以解決樹高的問題
度或階,每一個節點最多有多少個子節點,一般子節點的個數小于度的值
時間復雜度:0(logN)
在數據量相同的情況下,可以有效的控制樹高,也就是說可以使用更少的IO次數找到目標節點,從而提高數據庫的效率通過觀察,相同數據量的情況下,N叉樹的樹高可以得到有效的控制, 也就意味著在相同數據量的情況下可以減少IO的次數,從而提升效率。 但是MySQL認為N叉樹做為為索引的數據結構還不夠好。
B+樹
B+樹是一種經常用于數據庫和文件系統等場合的平衡查找樹,MySQL索引采用的數據結構,以4階B+樹為例,如下圖所示:
B+樹的特點！！！！！！
能夠保持數據穩定有序,插入與修改有較穩定的時間復雜度
非葉子節點僅具有索引作用,不存儲數據,所有葉子節點保真實數據
所有葉子節點構成一個有序鏈表,可以按照key排序的次序依次遍歷萬全部數據B+樹與B樹的對比！！！！
B+樹與B樹對比
1.葉子節點之間有一個相互連接的引用,可以通過一個葉子節點找到它相信的兄弟節點，MySQL在組織葉子節點時使用的是雙向鏈表
2.非葉子節點的值都包含在葉子節點中，MySQL非葉子節點只保存了對子節點的引用,沒有保存真實的數據,所有真實的數據都保存在葉子節點中
3.對于B+樹而言,在相同樹高的情況下,查找任一元素的時間復雜度都一樣,性能均衡時間復雜度:0(logN)：可以有效的控制樹高
MySQL中的頁
為什么要使用頁：
在.ibd文件中最重要的結構體就是Page(頁),頁是內存與磁盤交互的最小單元,默認大小為16KB，每次內存與磁盤的交互至少讀取一頁,所以在磁盤中每個頁內部的地址都是連續的,之所以這樣做,是因為在使用數據的過程中,根據局部性原理,將來要使用的數據大概率與當前訪問的數據在空間上是臨近的,所以一次從磁盤中讀取一頁的數據放入內存中,當下次查詢的數據還在這個頁中時就可以從內存中直接讀取,從而減少磁盤l/0提高性能！！！
Linux操作系統中管理文件的最小單位是4KB MySQL作為一個數據庫程序,以4KB大小管理數據顯然太少了,所以定義 了16KB一頁的默認頁大小當從內存中往磁盤里寫數據頁的時候,寫到一半操作系統掛了,這時MySQL應該如何保證數據安全?
在落盤之前會記錄各種日志,保證重啟之后可以找到沒有落盤的數據內容！！！！在MySQL中有多種不同類型的頁,最常用的就是用來存儲數據和索引引的"索引頁",也叫做"數據頁",但不論哪種類型的頁都會包含頁頭和頁尾,頁的主體信息使用數據"行"進行填充,數據頁的基本結構如下圖所示:
頁文件頭和頁文件尾
這里我們只關注,上一頁頁號和下一頁頁號,通過這兩個屬性可以把頁與頁之間鏈接起來,形成一個雙向鏈表。
通過頁號和頁大小,可以計算出下一頁和上一頁在磁盤上的偏移量
頁主體 頁目錄
頁主體部分是保存真實數據的主要區域,每當創建一個新頁,都會自動分配兩個行,一個是頁內最小行Infimun,另一個是頁內最大行Supremun,這兩個行并不存儲任何真實信息,而是做為
數據行鏈表的頭和尾,第一個數據行有一個記錄下一行的地址偏移量的區域next_record將頁
內所有數據行組成了一個單向鏈表,此時新頁的結構如下所示:
頁中的數據行是一個單向鏈表
頁目錄：
計算三層樹高的B+樹可以存放多少條記錄?
索引頁中存的是主鍵值和子節點的引用,也就是下一節點的偏移(地址)
主鍵bigint 8Byte,下一頁地址6Byte,也就是說一條索引記錄占8+6=14Byte
一個索引頁可以存16*1024/14=1170
理論上一個三層樹高的B+樹可以存:1170*1170*16=21,902,400條記錄在當前的場景下,表中有21,902,400條記錄的情況下,通過三次IO就可以完成數據的查詢
以上的I0過程,加載索引頁1-->加載索引頁2-->加載數據頁3? ?3次IO
把索引頁加載到內存中進行緩存,當查一條沒有加載過的數據時,一次真實IO就可以搞定這里查詢1次是因為 索引頁已經被緩存了 當索引內緩存到內存后 查詢數據時 會在內存中遍歷索引 這里沒有IO 通過索引來找到目標數據頁的磁盤地址,然后再從磁盤中進行IO讀取這里的IO表示的是磁盤IO 因為MySQL的數據其實是存在硬盤中的 這也就是在大型項目中為什么使用redis作為緩存的原因 因為從磁盤讀取數據太慢了 redis也是依靠內存的nosql數據庫 查詢起來會很快
索引分類?
1主鍵索引
自動創建索引,索引的值是主鍵列的值！！！
當在一個表上定義一個主鍵PRIMARYKEY時,InnoDB使用它作為聚集索引--聚簇索引
推薦為每個表定義一個主鍵。如果沒有邏輯上唯一且非空的列或列集可以使用主鍵,
則添加一個自增列。2普通索引
為了提升查詢效率,工作中通常為查詢頻繁的列創建索引
普通索引是最基本的索引類型,沒有唯一性的限制。可以包含一個列也可以包含多個列。
可能為多列創建組合索引,稱為復合索引或組全索引3.唯一索引
當在一個表上定義一個唯一鍵UNQUE時,自動創建唯一索引。
與普通索引類似,但區別在于唯一索引的列不允許有重復值。目的是為了去標識唯一性
4.全文索引
基于文本列上創建,以加快對這些列中包含的數據查詢和DML操作
用于全文搜索,僅MyISAM和InnoDB引擎支持。6.5聚集索引
與主鍵索引是同義詞
如果沒有為表定義PRIMARYKEY,InnoDB使用第一個UNIQUE和NOT NULL的列作為聚集索引。聚集索引可以標識數據行的唯一性
如果表中沒有PRIMARY KEY或合適的UNIQUE索引,InnoDB會為新插入的行生成一個行號并
用6字節的ROW_ID字段記錄,ROW_ID單調遞增,并使用ROW_ID做為索引。6非聚集索引
聚集索引以外的索引稱為非聚集索引或二級索引
二級索引中的每條記錄都包含該行的主鍵列,以及二級索引指定的列。
InnoDB使用這個主鍵值來搜索聚集索引中的行,這個過程稱為回表查詢
7索引覆蓋
當一個select語句使用了普通索引且查詢列表中的列剛好是創建普通索引時的所有或部分列,這時
就可以直接返回數據,而不用回表查詢,這樣的現象稱為索引覆蓋
)
