首先,正確的創建合適的索引,是提升資料庫查詢效能的基礎。
索引是什麼?
索引是為了加速資料行在資料行的擷取而建立的一種分散儲存的資料結構。
索引的工作機制是怎麼樣的?
如上圖中,如果現在有一個sql語句select * from teacher where id = 101,如果沒有索引的條件下,我們要找到這條記錄,我們就需要就行全表掃描,匹配id = 101的資料。如果有了索引,我們就可以快速的透過索引找到101所對應的行記錄在磁碟中的位址,再根據給定的位址取出對應的行資料。
MYSQL資料庫為什麼要使用B TREE作為索引的資料結構?
對資料的加速檢索,首先想到的是二元樹,二元樹的尋找時間複雜度可以達到O(log2(n))。下面看一下二元樹的儲存結構:
二元樹搜尋相當於一個二分查找。二元查找能大幅提升查詢的效率,但是它有一個問題:二元樹以第一個插入的資料作為根節點,如上圖中,如果只看右側,就會發現,就是一個線性鍊錶結構。如果我們現在的資料只包含1, 2, 3, 4,5, 6,就會出現一下情況:
如果我們要查詢的資料為6則需要遍歷所有的節點才能找到6,即,相當於全表掃描,就是由於有這種問題,所以二元查找樹不適合用來作為索引的資料結構。
基於這樣的推演,為了解決存在線性鍊錶的問題,很容易就能夠想到平衡二元查找樹。下面看看平衡二元樹是怎麼樣的:
#平衡二元查找樹定義為:節點的子節點高度差不能超過1,如上圖中的節點20,左節點高度為1,右邊節點高度0,差為1,所以上圖沒有違反定義,他就是平衡二元樹。確保二元樹平衡的方式為左旋,右旋等操作,至於若左旋右旋,可以自行去搜尋相關的知識。
如果上圖中平衡二元樹保存的是id索引,現在要從id = 8的數據,首先要把根節點加載進內存,用8和10進行比較,發現8比10小,繼續載入10的左子樹。把5裝進內存,用8和5比較,同理,載入5節點的右子樹。此時發現命中,現在要載入id為8的索引所對應的資料。
怎麼找到索引對應的資料呢?
索引保存資料的方式一般有兩種,第一種為在節點的資料區保存id = 8的行資料的所有資料具體內容。另外一種方式,資料區保存的是真正保存資料的磁碟位址。
到這裡,平衡二元樹解決了存在線性鍊錶的問題,資料查詢的效率好像也還可以,基本能達到O(log2(n)), 那為什麼mysql不選擇這樣的資料結構呢,他又存在什麼樣的問題呢?
問題1: 搜尋效率不足,一般來說,在樹結構中,資料所處的深度,決定了搜尋時的IO次數。如上圖搜尋id = 8的數據,需要進行3次IO。當資料量到達幾百萬的時候,樹的高度就會很恐怖。
問題2:查詢不不穩定,如果查詢的資料落在根節點,只需要一次IO,如果是葉子節點或是支節點,會需要多次IO才可以。
問題3: 節點儲存的資料內容太少。沒有很好利用作業系統和磁碟資料交換特性,也沒有利用好磁碟IO的預讀能力。因為作業系統和磁碟之間一次資料交換是已頁為單位的,一頁 = 4K,即每次IO作業系統會將4K資料載入進記憶體。但是,在二元樹每個節點的結構只保存一個關鍵字,一個資料區,兩個子節點的引用,並不能夠填滿4K的內容。幸好苦苦做了一次的IO操作,卻只載入了一個關鍵字,在樹的高度很高,剛好又搜尋的關鍵字位於葉子節點或支節點的時候,取一個關鍵字要做很多次的IO。
那有沒有一種結構能夠解決二元樹的這種問題呢?
有,多路平衡查找樹:(Balance Tree):
B Tree 是絕對平衡樹,所有的葉子節點在同一高度,如下圖所示:
B Tree有什麼優勢,又是怎麼去解決一些問題的呢?
先看定義,上圖為一個2-3樹(每個節點儲存2個關鍵字,有3路),多路平衡找出樹也就是多叉的意思,從上圖中可以看出,每個節點保存的關鍵字的個數和路數關係為:
關鍵字個數= 路數– 1。
假設要從上圖中去尋找id = 28的數據,B TREE 搜尋過程如下:
先把根節點載入進內存,載入了17,35兩個關鍵字,判斷規則為:
根據上述規則命中28後,接下來載入28對應的數據, 就去找28對應的資料區,資料區中儲存的是具體的數據或者是指向數據的指標。
為什麼說這種結構能夠解決平衡二元樹存在的問題呢?
能夠很好的利用作業系統和磁碟的互動特性, MYSQL為了很好的利用磁碟的預讀能力,將頁大小為16K,即將一個節點(磁碟區塊)的大小設置為16K,一次IO將一個節點(16K)內容載入進記憶體。這裡,假設關鍵字類型為int,即4字節,若每個關鍵字對應的資料區也是4字節,不考慮子節點引用的情況下,則上圖中的每個節點大約能夠儲存( 16 * 1000)/ 8 = 2000個關鍵字,則共2001個路數。對於二元樹,三層高度,最多可以保存7個關鍵字,而對於這種有2001路的B樹,三層高度能夠搜尋的關鍵字個數遠遠的大於二元樹。
在B TREE保證樹的平衡的過程中,每次關鍵字的變化,都會導致結構發生很大的變化,這個過程是特別浪費時間的,所以創建索引一定要創建合適的索引,而不是把所有的字段都創建索引,創建冗餘索引只會在對資料進行新增,刪除,修改時增加效能消耗。
既然B樹已經很好的解決了問題,為什麼MYSQL還要用B TREE?
先看看B TREE是怎樣的,B TREE是B TREE的變種,在B 樹種,B樹種的路數和關鍵字的個數的關係不再成立了,B在TREE中,資料檢索規則採用的是左閉合區間,路數和關鍵個數關係為1比1,具體如下圖所示:
B TREE和B TREE差別是什麼?
1、B TREE 關鍵字的搜尋採用的是左閉合區間,之所以採用左閉合區間是因為他要最好的去支援自增id,這也是mysql的設計初衷。即,如果id = 1命中,會繼續往下查找,直到找到葉子節點中的1。 2、B TREE 根節點和支節點沒有資料區,關鍵字對應的資料只保存在葉子節點中。也就是只有葉子節點中的關鍵字資料區才會保存真正的資料內容或是內容的位址。而在B樹種,如果根節點命中,則會直接回傳資料。並且在B TREE中,葉子節點不會去保存子節點的引用。 3、B TREE葉子節點是順序排列的,並且相鄰的節點具有順序引用的關係,如上圖中葉子節點之間有指標相連接。MYSQL為什麼最後要去選擇B TREE?
1、B TREE是B TREE的變種,B TREE能解決的問題,B TREE也能夠解決(降低樹的高度,增大節點儲存資料量) 2. B TREE掃庫和掃表能力更強,如果我們要根據索引去進行資料表的掃描,對B TREE進行掃描,需要把整棵樹遍歷一遍,而B TREE只需要遍歷他的所有葉子節點即可(葉子節點之間有引用)。 3、B TREE磁碟讀寫能力更強,他的根節點和支節點不保存資料區,所有根節點和支節點同樣大小的情況下,保存的關鍵字要比B TREE要多。而葉節點不保存子節點引用。所以,B TREE讀寫一次磁碟載入的關鍵字比B TREE更多。 4、B TREE排序能力更強,如上面的圖可以看出,B TREE天然具有排序功能。 5、B TREE查詢效率更穩定,每次查詢數據,查詢IO次數一定是穩定的。當然這個每個人的理解都不同,因為在B TREE如果根節點命中直接返回,確實效率更高。MYSQL B TREE具體落實形式#
這裡主要講解的是MYSQL根據B TREE索引結構不同的兩種儲存引擎(MYISAM 和INNODB)的實現,首先找到MYSQL保存資料的資料夾,看看mysql是如何保存資料的:
進入到這個目錄下,這個目錄下保存的是所有資料庫,然後再進入到具體的一個資料庫目錄下。在這裡,有多種資料的儲存引擎,這裡講解MYISAM和innodb,如圖中所示:
#MYISAM儲存引擎索引:
##從圖中可以看出,使用MYISAM儲存引擎儲存資料庫數據,一共有三個檔案:Frm,表格的定義檔。 MYD:資料文件,所有的資料都保存在這個文件中。 MYI:索引檔。 在MYISAM儲存引擎中,資料和索引的關係如下:在innodb中,輔助索引的格式如下圖所示?
為什麼說離散型越高,選擇型越好?
如下圖,如果對Sex建立索引,則索引結構將會如下:當進行配對的時候,會把字串轉換成ascll碼,如abc變成97 98 99,然後從左往右一個字元一個字元進行比較。所以在sql查詢中使用like %a 時候索引會失效,因為%表示全匹配,如果已經全匹配就不需要索引,不如直接全表掃描。
3、最少空間原則
前面已經說過,當關鍵字佔用的空間越小,則每個節點保存的關鍵字個數就越多,每次加載進內存的關鍵字個數就越多,檢索效率就越高。
聯合索引:
單列索引:節點中的關鍵字[name]
#聯合索引:節點中的關鍵字[name, phoneNum]
可以把單列索引看成特殊的聯合索引,聯合索引的比較也是根據最左邊匹配原則。
聯合索引列的選擇原則:
(1) 常用的列優先(最左匹配原則)
#(2) 離散度高的列優先(離散度高原則)
(3) 寬度小的列優先,(最少空間原則)
下面簡單舉例平時常會遇到的問題:
#如,平時常用的查詢sql如下:
Select * from users where name = ?
Select * from users where name = ? and pahoneNum = ?
為了加快檢索速度,為上面的查詢sql建立索引如下:
Create index idx_name on users(name)
Create index idx_name_phoneNum on users(name, phoneNum)
在上面解決方案中,根據最左匹配原則,idx_name為冗餘索引, where name = ?同樣可以利用索引idx_name_phoneNum進行檢索。冗餘索引會增減維護B TREE平衡時的效能消耗,並且佔用磁碟空間。
覆寫索引:
如果查詢的列,透過索引項目的資訊可直接傳回,則該索引稱為查詢SQL的覆蓋索引。覆蓋索引可以提高查詢的效率。
下面透過範例說明覆蓋索引。
表:teacher
#:PK(id), key(name,phoneNum), unique(teacherNo)
下面哪些sql使用到了覆蓋索引?
Select teacherNo from teacher where teacherNo = ?
:使用到了,檢索到teacherNo 時候,可以直接將索引中的teacherNo 值傳回,不需要進入資料區。
Select id,teacherNo from teacher where teacherNo = ?
:使用到了,輔助索引的葉子節點保存了主索引的值,所以檢索到輔助索引的葉子節點的時候就可以之間返回id。
Select name,phoneNum from teacher where teacherNo = ?
:沒有用到
Select phoneNum from teacher where name = ?
, 使用到了。
知道了覆蓋索引,就知道了為什麼sql中要求盡量不要使用select *,要寫明具體要查詢的字段,一個原因就是,這樣在使用到覆蓋索引的情況下,不需要進入到資料區,資料就能直接返回,提升了查詢效率。
透過前面的學習,我們可以很容易的明白如下一下結論:
1、索引列的資料長度滿足業務的情況下能少則少。
2、表中的索引並不是越多越好。
3、Where 條件中,like 9%, like %9%, like%9,三種方式都用不到索引。後兩種方式對於索引是無效的。第一種9%是不確定的,決定於列的離散型,結論上講可以用到,如果發現離散情況特別差的情況下,查詢優化器覺得走索引查詢性能更差,還不如全表掃描。
4、Where條件中 NOT IN 無法使用索引
5、多用指定查詢,只回傳自己想要的列,少用select *。
6、查詢條件中使用函數,索引將會失效,這和列的離散型有關,一旦使用到函數,函數具有不確定性。
7、聯合索引中,如果不是依照索引最左列開始查找,無法使用索引。
8、對聯合索引精確匹配最左前列併範圍匹配另一列,可以使用到索引。
9、聯合索引中,如果查詢有某個欄位的範圍查詢,其右邊所有的欄位都無法使用索引。
推薦Mysql教學《Mysql教學》
以上是深入理解Mysql的B+Tree索引原理的詳細內容。更多資訊請關注PHP中文網其他相關文章!

本篇文章给大家带来了关于mysql的相关知识,其中主要介绍了关于架构原理的相关内容,MySQL Server架构自顶向下大致可以分网络连接层、服务层、存储引擎层和系统文件层,下面一起来看一下,希望对大家有帮助。

mysql的msi与zip版本的区别:1、zip包含的安装程序是一种主动安装,而msi包含的是被installer所用的安装文件以提交请求的方式安装;2、zip是一种数据压缩和文档存储的文件格式,msi是微软格式的安装包。

方法:1、利用right函数,语法为“update 表名 set 指定字段 = right(指定字段, length(指定字段)-1)...”;2、利用substring函数,语法为“select substring(指定字段,2)..”。

在mysql中,可以利用char()和REPLACE()函数来替换换行符;REPLACE()函数可以用新字符串替换列中的换行符,而换行符可使用“char(13)”来表示,语法为“replace(字段名,char(13),'新字符串') ”。

转换方法:1、利用cast函数,语法“select * from 表名 order by cast(字段名 as SIGNED)”;2、利用“select * from 表名 order by CONVERT(字段名,SIGNED)”语句。

本篇文章给大家带来了关于mysql的相关知识,其中主要介绍了关于MySQL复制技术的相关问题,包括了异步复制、半同步复制等等内容,下面一起来看一下,希望对大家有帮助。

在mysql中,可以利用REGEXP运算符判断数据是否是数字类型,语法为“String REGEXP '[^0-9.]'”;该运算符是正则表达式的缩写,若数据字符中含有数字时,返回的结果是true,反之返回的结果是false。

本篇文章给大家带来了关于mysql的相关知识,其中主要介绍了mysql高级篇的一些问题,包括了索引是什么、索引底层实现等等问题,下面一起来看一下,希望对大家有帮助。


熱AI工具

Undresser.AI Undress
人工智慧驅動的應用程序,用於創建逼真的裸體照片

AI Clothes Remover
用於從照片中去除衣服的線上人工智慧工具。

Undress AI Tool
免費脫衣圖片

Clothoff.io
AI脫衣器

AI Hentai Generator
免費產生 AI 無盡。

熱門文章

熱工具

SublimeText3 Mac版
神級程式碼編輯軟體(SublimeText3)

PhpStorm Mac 版本
最新(2018.2.1 )專業的PHP整合開發工具

WebStorm Mac版
好用的JavaScript開發工具

ZendStudio 13.5.1 Mac
強大的PHP整合開發環境

MinGW - Minimalist GNU for Windows
這個專案正在遷移到osdn.net/projects/mingw的過程中,你可以繼續在那裡關注我們。 MinGW:GNU編譯器集合(GCC)的本機Windows移植版本,可自由分發的導入函式庫和用於建置本機Windows應用程式的頭檔;包括對MSVC執行時間的擴展,以支援C99功能。 MinGW的所有軟體都可以在64位元Windows平台上運作。