Mysql InnoDB b+樹的高度

為什么Mysql考慮使用B+樹，而不是B樹，其實(shí)我們可以先了解下B樹和B+樹的特點(diǎn)來看下。

成都創(chuàng)新互聯(lián)堅(jiān)持“要么做到，要么別承諾”的工作理念，服務(wù)領(lǐng)域包括：網(wǎng)站建設(shè)、成都網(wǎng)站建設(shè)、企業(yè)官網(wǎng)、英文網(wǎng)站、手機(jī)端網(wǎng)站、網(wǎng)站推廣等服務(wù)，滿足客戶于互聯(lián)網(wǎng)時(shí)代的豐滿網(wǎng)站設(shè)計(jì)、移動媒體設(shè)計(jì)的需求，幫助企業(yè)找到有效的互聯(lián)網(wǎng)解決方案。努力成為您成熟可靠的網(wǎng)絡(luò)建設(shè)合作伙伴！

※ 樹的每個(gè)結(jié)點(diǎn)都會存儲數(shù)據(jù)

※ 單次查詢不一定要遍歷到樹的根部，平均查詢時(shí)間會比較快

※ 非葉子節(jié)點(diǎn)不存儲數(shù)據(jù)，只存儲（冗余）索引，索引包含主鍵和指針

※ 葉子節(jié)點(diǎn)才真正存儲數(shù)據(jù)

※ 每個(gè)葉子節(jié)點(diǎn)互相鏈表相連，保證了范圍查詢的時(shí)效性(頁之間用雙向鏈表連接，數(shù)據(jù)間用單項(xiàng)鏈表鏈接)

InnoDB最小存儲單位是頁，葉子節(jié)點(diǎn)和非葉子節(jié)點(diǎn)最小單位都是頁，頁大小Mysql 默認(rèn)設(shè)定16384字節(jié)，約為16KB。

我們假設(shè)主鍵ID為bigint類型，長度為8字節(jié)，而指針大小在InnoDB源碼中設(shè)置為6字節(jié)，這樣一共14字節(jié)

我們一個(gè)頁中能存放多少這樣的索引元素，其實(shí)就代表有多少指針，即16384/14=1170;

高度為2的B+樹能存放1170×16=18720

高度為3的B+樹能存放1170×1170×16 = 21902400

InnoDB中B+樹高度一般為1-3層，它就能滿足千萬級的數(shù)據(jù)存儲。

在查找數(shù)據(jù)時(shí)一次頁的查找代表一次IO，所以通過主鍵索引查詢通常只需要1-3次IO操作即可查找到數(shù)據(jù)。

MYSQL 那點(diǎn)破事！索引、SQL調(diào)優(yōu)、事務(wù)、B+樹、分表 ....

大家好，我是Tom哥~

為了便于大家查找問題，了解全貌，整理個(gè)目錄，我們可以快速全局了解關(guān)于mysql數(shù)據(jù)庫，面試官一般喜歡問哪些問題

接下來，我們逐條來看看每個(gè)問題及答案

MyISAM 和 InnoDB 的區(qū)別？

答案：InnoDB 支持 事務(wù)、外鍵、聚集索引，通過MVCC來支持高并發(fā)，索引和數(shù)據(jù)存儲在一起。InnoDB 不保存表的具體行數(shù)，執(zhí)行 select count(*) from table 時(shí)需要全表掃描。而MyISAM 用一個(gè)變量保存了整個(gè)表的行數(shù)。

InnoDB 最小的鎖粒度是行鎖，MyISAM 最小的鎖粒度是表鎖，并發(fā)能力低。MySQL 將默認(rèn)存儲引擎是 InnoDB

mysql 鎖有哪些類型？

答案：mysql鎖分為共享鎖( S lock ) 、排他鎖 ( X lock )，也叫做讀鎖和寫鎖。根據(jù)粒度，可以分為表鎖、頁鎖、行鎖。

什么是間隙鎖？

答案：間隙鎖是可重復(fù)讀級別下才會有的鎖，mysql會幫我們生成了若干 左開右閉 的區(qū)間，結(jié)合MVCC和間隙鎖可以解決幻讀問題。

如何避免死鎖？

答案：死鎖的四個(gè)必要條件：1、互斥 2、請求與保持 3、環(huán)路等待 4、不可剝奪。

數(shù)據(jù)庫的隔離級別？

答案：讀未提交、讀已提交、可重復(fù)讀（mysql的默認(rèn)級別，每次讀取結(jié)果都一樣，但是有可能產(chǎn)生幻讀）、串行化。

Mysql有哪些類型的索引？

答案：

什么是覆蓋索引和回表？

答案：

1、覆蓋索引，指的是在一次查詢中，一個(gè)索引包含所有需要查詢的字段的值，可能是返回值或where條件

假如我們創(chuàng)建了一個(gè)(money，buyer_id)的聯(lián)合索引，索引的葉子節(jié)點(diǎn)包含了 buyer_id 的信息，則不會再 回表 查詢。

2、回表，指查詢時(shí)一些字段值拿不到，需要到主鍵索引B+樹再查一次。

Mysql的最左前綴原則？

答案：即最左優(yōu)先，在檢索數(shù)據(jù)時(shí)從聯(lián)合索引的最左邊開始匹配，直到遇到范圍查詢（如： 、 、between、like等）

例子：where a = 1 and b = 2 and c 3 and d = 4 ，如果建立(a,b,c,d)組合索引，d是用不到索引的；如果建立(a,b,d,c)的索引則都可以用到，a,b,d的順序可以任意調(diào)整。

線上SQL的調(diào)優(yōu)經(jīng)驗(yàn)？

答案：

官方為什么建議采用自增id 作為主鍵？

答案：自增id是連續(xù)的，插入過程也是順序的，總是插入在最后，減少了頁分裂，有效減少數(shù)據(jù)的移動。所以盡量不要使用字符串（如：UUID）作為主鍵。

索引為什么采用B+樹，而不用B-樹，紅黑樹？

答案：提升查詢速度，首先要減少磁盤IO次數(shù)，也就是要降低樹的高度。

事務(wù)的特性有哪些？

答案：ACID。

如何實(shí)現(xiàn)分布式事務(wù)？

答案：

日常工作中，MySQL 如何做優(yōu)化？

答案：

mysql 主從同步具體過程？

答案：

什么是主從延遲？

答案：指一個(gè)寫入SQL操作在主庫執(zhí)行完后，將數(shù)據(jù)完整同步到從庫會有一個(gè)時(shí)間差，稱之為主從延遲。計(jì)算公式：

注意：不同服務(wù)器要保持時(shí)鐘一致

主從延遲排查方法？

答案：通過 show slave status 命令輸出的 Seconds_Behind_Master 參數(shù)的值來判斷

主從延遲要怎么解決？

答案：

如果數(shù)據(jù)量太大怎么辦？

答案：mysql表的數(shù)據(jù)量一般控制在千萬級別，如果再大的話，就要考慮分庫分表。除了分表外，列舉了面對海量數(shù)據(jù)業(yè)務(wù)的一些常見優(yōu)化手段

分表后ID如何保證全局唯一呢？

答案：分庫分表后，多張表共用一套全局id，原來單表主鍵自增方式滿足不了要求。我們需要重新設(shè)計(jì)一套id生成器。特點(diǎn)：全局唯一、高性能、高可用、方便接入。

分表后可能遇到的哪些問題？

答案：分表后，與單表的最大區(qū)別是有分表鍵 sharding_key ，用來路由具體的物理表，以電商為例，有買家和賣家兩個(gè)維度，以 buyer_id 路由，無法滿足賣家的需求，反之同樣道理。如何解決？

MySQL_索引樹

查看樹插入刪除圖解：

時(shí)間復(fù)雜度：O(N)

時(shí)間復(fù)雜度：O(logn)

如果數(shù)據(jù)插入是遞增或者遞減順序的話，會使樹成為鏈?zhǔn)浇Y(jié)構(gòu)。 時(shí)間復(fù)雜度：O(N)

為了保證平衡，在插入或者刪除的時(shí)候必須要旋轉(zhuǎn)，通過插入或者刪除性能的損失來彌補(bǔ)查詢性能的提升。

但如果寫請求和讀請求一樣多的時(shí)候怎么辦？

隨著數(shù)據(jù)的插入，樹的深度會變深，樹的深度越深，意味著 IO 次數(shù)越多。影響數(shù)據(jù)讀取的效率。

MySQL 的頁大小是16k。假設(shè)只有data 占用空間且占用 1k 一個(gè)磁盤塊可以放置16條記錄，三層就是 4096條記錄?？隙ㄐ∮?4096.

如果想要放入更多的數(shù)據(jù)的化，得加層。加層 IO 量肯定上來了。

data 太占內(nèi)存，導(dǎo)致存儲數(shù)據(jù)太少。

MySQL加載索引是以磁盤塊（頁）為單位的，頁（Page）是 Innodb 存儲引擎用于管理數(shù)據(jù)的最小磁盤單位。默認(rèn)的頁大小為 16KB。

假設(shè)只有 p1+key 值 占用空間且占用 10字節(jié)， 一個(gè)磁盤塊可以放置1600條記錄，三層就是 40960000條記錄。

在B+樹 上有兩個(gè)頭節(jié)點(diǎn)，一個(gè)指向根節(jié)點(diǎn)，另一個(gè)指向關(guān)鍵字最小的葉子節(jié)點(diǎn)，而且所有的葉子節(jié)點(diǎn)（即數(shù)據(jù)節(jié)點(diǎn)）之間是一種鏈?zhǔn)江h(huán)結(jié)構(gòu)，因此可以對 B+樹 進(jìn)行兩種查找運(yùn)算：一種是對于主鍵的范圍查找和分頁查找，另一種是從根節(jié)點(diǎn)開始，進(jìn)行隨機(jī)查找。

讓當(dāng)前key值盡可能的少占用存儲空間，才能保證存儲更多的值。降低樹的高度，減少IO。

保證key的長度越小越好。

mysql 查詢樹形接口sql

mysql啊，這個(gè)還真不知道可不可以。不過oracle可以，遞歸查詢上上級，或者查詢到下下級都可以。代碼參考：

查詢出員工號為7788的所有上級。

select * from scott.emp start with empno=7788 connect by prior mgr= empno;

mysql里面如果sql不能實(shí)現(xiàn)，那就用程序里面的list啊，查詢一個(gè)添加一個(gè)，循環(huán)（while）直到它的上級id為空為止。

事實(shí)上更建議用程序的方法，程序?qū)懘a更靈活，而sql不必寫的太復(fù)雜。

MySQL怎么查詢樹形結(jié)構(gòu)的表的數(shù)據(jù)

一般比較普遍的就是四種方法：（具體見 SQL Anti-patterns這本書）

Adjacency List：每一條記錄存parent_id

Path Enumerations：每一條記錄存整個(gè)tree path經(jīng)過的node枚舉

Nested Sets：每一條記錄存 nleft 和 nright

Closure Table：維護(hù)一個(gè)表，所有的tree path作為記錄進(jìn)行保存。