你管這破玩意叫 B+ 樹?

從實際需求出發(fā)

CREATE?TABLE?`user`?(
??`id`?int(11)?unsigned?NOT?NULL?AUTO_INCREMENT,
??`name`?int(11)?DEFAULT?NULL?COMMENT?'姓名',
??`age`?tinyint(3)?unsigned?DEFAULT?NULL?COMMENT?'年齡',
??`height`?int(11)?DEFAULT?NULL?COMMENT?'身高',
??PRIMARY?KEY?(`id`)
)?ENGINE=InnoDB?DEFAULT?CHARSET=utf8?COMMENT='用戶表';

1.?select?*?from?user?where?id?=?xxx
2.?select?*?from?user?order?by?id?asc/desc
3.?select?*?from?user?where?age?=?xxx
4.?select?age?from?user?where?age?=?xxx
5.?select?age?from?user?order?by?age?asc/desc

insert?into?user?('name',?'age',?'height')?values?('張三',?20,?170);
insert?into?user?('name',?'age',?'height')?values?('李四',?21,?171);
insert?into?user?('name',?'age',?'height')?values?('王五',?22,?172);
insert?into?user?('name',?'age',?'height')?values?('趙六',?23,?173);
insert?into?user?('name',?'age',?'height')?values?('錢七',?24,?174);

select?*?from?user?where?id?=?3

頁

頁目錄

1. 定位在哪個槽，首先取最小槽和最大槽對應(yīng)的 id（分別為 4， 12），先通過二分查找取它們的中間值為 (4+12)/2 = 8，8 小于 9，且槽 2 的最大 id 為 12，所以可知 id = 9 的記錄在槽 2 里

2. 遍歷槽 2 中的元素，現(xiàn)在問題來了，我們知道每條記錄都構(gòu)成了一個單鏈表，而每個槽指向的是此分組中的最大 id 值，該怎么從此槽的第一個元素開始遍歷呢，很簡單，從槽 1 開始遍歷不就行了，因為它指向元素的下一個元素即為槽 2 的起始元素，遍歷后發(fā)現(xiàn)槽 2 的 第一個元素即為我們找到的 id 為 9 的元素

B+ 樹的誕生

• 如果B+樹只有 1 層，也就是只有 1 個用于存放用戶記錄的節(jié)點，最多能存放100條記錄。

• 如果B+樹有 2 層，最多能存放1000×100=100000條記錄。

• 如果B+樹有 3 層，最多能存放1000×1000×100=100000000條記錄。

• 如果B+樹有 4 層，最多能存放1000×1000×1000×100=100000000000條記錄！

聚簇索引與非聚簇索引

select?*?from?user?where?age?=?xxx

select?age?from?user?where?age?=?xxx
select?age,id?from?user?where?age?=?xxx

磁盤的構(gòu)造

1. 尋道：既然數(shù)據(jù)是保存在扇區(qū)上的，那我首先我們需要知道它到底是在哪個扇區(qū)上吧，這就需要先讓磁頭移動到扇區(qū)所在的磁道上，我們把它稱為尋道時間，平均尋道時間一般在3-15ms

2. 旋轉(zhuǎn)延遲: 磁盤移動到扇區(qū)所在的磁盤上時，此時的磁頭對準的還不一定我們想要的數(shù)據(jù)對應(yīng)的扇區(qū)，所以需要等待盤片旋轉(zhuǎn)片刻，等到我們想要的數(shù)據(jù)對應(yīng)的扇區(qū)落到磁頭下，旋轉(zhuǎn)延遲取決于磁盤轉(zhuǎn)速，通常用磁盤旋轉(zhuǎn)一周所需時間的1/2表示。比如：7200rpm的磁盤平均旋轉(zhuǎn)延遲大約為60*1000/7200/2 = 4.17ms，而轉(zhuǎn)速為15000rpm的磁盤其平均旋轉(zhuǎn)延遲為2ms

3. 數(shù)據(jù)傳輸:經(jīng)過前面的兩步，磁頭終于開始讀寫數(shù)據(jù)了，目前IDE/ATA能達到133MB/s，SATA II可達到300MB/s的接口數(shù)據(jù)傳輸率，數(shù)據(jù)傳輸時間通常遠小于前兩部分消耗時間?？珊雎圆挥?/p>

總結(jié)

• 巨人的肩膀

1. 磁盤I/O那些事: https://tech.meituan.com/2017/05/19/about-desk-io.html

2. 帶你從頭到尾捋一遍MySQL索引結(jié)構(gòu): https://blog.51cto.com/u_12302929/3290492

3. MySQL 是怎樣運行的：從根兒上理解 MySQL