100w的數(shù)據(jù)表比1000w的數(shù)據(jù)表查詢更快嗎？

當(dāng)我們對一張表發(fā)起查詢的時(shí)候，是不是這張表的數(shù)據(jù)越少，查詢的就越快？

答案是不一定，這和mysql B+數(shù)索引結(jié)構(gòu)有一定的關(guān)系。

innodb邏輯存儲結(jié)構(gòu)

從Innodb存儲引擎的邏輯存儲結(jié)構(gòu)來看，所有數(shù)據(jù)都被邏輯的放在一個(gè)表空間（tablespace）中，默認(rèn)情況下，所有的數(shù)據(jù)都放在一個(gè)表空間中，當(dāng)然也可以設(shè)置每張表單獨(dú)占用一個(gè)表空間，通過innodb_file_per_table來開啟。

mysql> show variables like 'innodb_file_per_table';
+-----------------------+-------+
| Variable_name         | Value |
+-----------------------+-------+
| innodb_file_per_table | ON    |
+-----------------------+-------+
1 row in set (0.00 sec)

表空間又是由各個(gè)段組成的，常見的有數(shù)據(jù)段，索引段，回滾段等。因?yàn)閕nnodb的索引類型是b+樹，那么數(shù)據(jù)段就是葉子結(jié)點(diǎn)，索引段為b+的非葉子結(jié)點(diǎn)。

段空間又是由區(qū)組成的，在任何情況下，每個(gè)區(qū)的大小都為1M，innodb引擎一般默認(rèn)頁的大小為16k，一般一個(gè)區(qū)中有64個(gè)連續(xù)的頁（64*16k=1M）。

通過段我們知道，還存在一個(gè)最小的存儲單元頁。它是innodb管理的最小的單位，默認(rèn)是16K，當(dāng)然也可以通過innodb_page_size來設(shè)置為4K、8K...，我們的數(shù)據(jù)都是存在頁中的

mysql> show variables like 'innodb_page_size';
+------------------+-------+
| Variable_name    | Value |
+------------------+-------+
| innodb_page_size | 16384 |
+------------------+-------+
1 row in set (0.00 sec)

所以innodb的數(shù)據(jù)結(jié)構(gòu)應(yīng)該大致如下：

B+ 樹

b+樹索引的特點(diǎn)就是數(shù)據(jù)存在葉子結(jié)點(diǎn)上，并且葉子結(jié)點(diǎn)之間是通過雙向鏈表方式組織起來的。

假設(shè)存在這樣一張表：

CREATE TABLE `user` (
  `id` bigint(20) unsigned NOT NULL AUTO_INCREMENT,
  `name` varchar(100) NOT NULL DEFAULT '',
  `age` int(10) NOT NULL DEFAULT 0,
  PRIMARY KEY (`id`),
  KEY `name` (`name`)
) ENGINE=InnoDB AUTO_INCREMENT=1 DEFAULT CHARSET=utf8mb4;

聚集索引

對于主鍵索引id，假設(shè)它的b+樹結(jié)構(gòu)可能如下：

• 此時(shí)樹的高度是2
• 葉子節(jié)點(diǎn)之間雙向鏈表連接
• 葉子結(jié)點(diǎn)除了id外，還存了name、age字段（葉子結(jié)點(diǎn)包含整行數(shù)據(jù)）

我們來看看 select * from user where id=30 是如何定位到的。

• 首先根據(jù)id=30，判斷在第一層的25-50之間
• 通過指針找到在第二層的p2中
• 把p2再加載到內(nèi)存中
• 通過二分法找到id=30的數(shù)據(jù)

總結(jié)：可以發(fā)現(xiàn)一共發(fā)起兩次io，最后加載到內(nèi)存檢索的時(shí)間忽略不計(jì)?？偤臅r(shí)就是兩次io的時(shí)間。

非聚集索引

通過表結(jié)構(gòu)我們知道，除了id，我們還有name這個(gè)非聚集索引。所以對于name索引，它的結(jié)構(gòu)可能如下：

• 此時(shí)樹的高度是2
• 葉子節(jié)點(diǎn)之間雙向鏈表連接
• 葉子結(jié)點(diǎn)除了name外，還有對應(yīng)的主鍵id

我們來看看 select * from user where name=jack 是如何定位到的。

• 首先根據(jù) name=jack，判斷在第一層的mary-tom之間
• 通過指針找到在第二層的p2中
• 把p2再加載到內(nèi)存中
• 通過二分法找到name=jack的數(shù)據(jù)（只有name和id）
• 因?yàn)槭?code style="font-size: 14px;word-wrap: break-word;padding: 2px 4px;border-radius: 4px;margin: 0 2px;color: #1e6bb8;background-color: rgba(27,31,35,.05);font-family: Operator Mono, Consolas, Monaco, Menlo, monospace;word-break: break-all;">select *，所以通過id再去主鍵索引查找
• 同樣的原理最終在主鍵索引中找到所有的數(shù)據(jù)

總結(jié)：name查詢兩次io，然后通過id再次回表查詢兩次io，加載到內(nèi)存的時(shí)間忽略不計(jì)，總耗時(shí)是4次io。

一棵樹能存多少數(shù)據(jù)

以上面的user表為例，我們先看看一行數(shù)據(jù)大概需要多大的空間：通過show table status like 'user'\G

mysql> show table status like 'user'\G
*************************** 1. row ***************************
           Name: user
         Engine: InnoDB
        Version: 10
     Row_format: Dynamic
           Rows: 10143
 Avg_row_length: 45
    Data_length: 458752
Max_data_length: 0
   Index_length: 311296
      Data_free: 0
 Auto_increment: 10005
    Create_time: 2021-07-11 17:22:56
    Update_time: 2021-07-11 17:31:52
     Check_time: NULL
      Collation: utf8mb4_general_ci
       Checksum: NULL
 Create_options:
        Comment:
1 row in set (0.00 sec)

我們可以看到Avg_row_length=45，那么一行數(shù)據(jù)大概占45字節(jié)，因?yàn)橐豁摰拇笮∈?6k，那么一頁可以存儲的數(shù)據(jù)是16k/45b = 364行數(shù)據(jù)，這是葉子結(jié)點(diǎn)的單page存儲量。

以主鍵索引id為例，int占用4個(gè)字節(jié)，指針大小在InnoDB中占6字節(jié)，這樣一共10字節(jié)，從root結(jié)點(diǎn)出來多少個(gè)指針，就可以知道root的下一層有多少個(gè)頁。因?yàn)閞oot結(jié)點(diǎn)只有一頁，所以此時(shí)就是16k/10b = 1638個(gè)指針。

• 如果樹的高度是2，那么能存儲的數(shù)據(jù)量就是1638 * 364 = 596232條
• 如果樹的高度是3，那么能存儲的數(shù)據(jù)量就是1638 * 1638 * 364 = 976628016條

如何知道一個(gè)索引樹的高度

innodb引擎中，每個(gè)頁都包含一個(gè)PAGE_LEVEL的信息，用于表示當(dāng)前頁所在索引中的高度。默認(rèn)葉子節(jié)點(diǎn)的高度為0，那么root頁的PAGE_LEVEL + 1就是這棵索引的高度。

那么我們只要找到root頁的PAGE_LEVEL就行了。

通過以下sql可以定位user表的索引的page_no:

mysql> SELECT b.name, a.name, index_id, type, a.space, a.PAGE_NO  FROM information_schema.INNODB_SYS_INDEXES a,  information_schema.INNODB_SYS_TABLES b  WHERE a.table_id = b.table_id AND a.space <> 0 and b.name='test/user';
+-----------+---------+----------+------+-------+---------+
| name      | name    | index_id | type | space | PAGE_NO |
+-----------+---------+----------+------+-------+---------+
| test/user | PRIMARY |      105 |    3 |    67 |       3 |
| test/user | name    |      106 |    0 |    67 |       4 |
+-----------+---------+----------+------+-------+---------+
2 rows in set (0.00 sec)

可以看到主鍵索引的page_no=3，因?yàn)?code style="font-size: 14px;word-wrap: break-word;padding: 2px 4px;border-radius: 4px;margin: 0 2px;color: #1e6bb8;background-color: rgba(27,31,35,.05);font-family: Operator Mono, Consolas, Monaco, Menlo, monospace;word-break: break-all;">PAGE_LEVEL在每個(gè)頁的偏移量64位置開始，占用兩個(gè)字節(jié)。所以算出它在文件中的偏移量：16384*3 + 64 = 49152 + 64 =49216，再取前兩個(gè)字節(jié)就是root的PAGE_LEVEL了。

通過以下命令找到ibd文件目錄

show global variables like "%datadir%" ;
+---------------+-----------------------+
| Variable_name | Value                 |
+---------------+-----------------------+
| datadir       | /usr/local/var/mysql/ |
+---------------+-----------------------+
1 row in set (0.01 sec)

user.ibd在 /usr/local/var/mysql/test/下。

通過hexdump來分析data文件。

hexdump -s 49216 -n 10  user.ibd
000c040 00 01 00 00 00 00 00 00 00 69
000c04a

000c040 00 01 00 00 00 00 00 00 00 69

00 01就是說明PAGE_LEVEL=1，那么樹的高度就是1+1=2。

回到題目

100w的數(shù)據(jù)表比1000w的數(shù)據(jù)表查詢更快嗎？通過查詢的過程我們知道，查詢耗時(shí)和樹的高度有很大關(guān)系。如果100w的數(shù)據(jù)如果和1000w的數(shù)據(jù)的樹的高度是一樣的，那其實(shí)它們的耗時(shí)沒什么區(qū)別。

來源：juejin.cn/post/6984034503362609165