面試題:InnoDB中一棵B+樹能存多少行數據?

来源:https://www.cnblogs.com/wuneng/archive/2019/09/03/11455327.html
-Advertisement-
Play Games

1.一個問題 InnoDB一棵B+樹可以存放多少行數據?這個問題的簡單回答是:約2千萬。為什麼是這麼多呢?因為這是可以算出來的,要搞清楚這個問題,我們先從InnoDB索引數據結構、數據組織方式說起。 我們都知道電腦在存儲數據的時候,有最小存儲單元,這就好比我們今天進行現金的流通最小單位是一毛。在計 ...


1.一個問題

InnoDB一棵B+樹可以存放多少行數據?這個問題的簡單回答是:約2千萬。為什麼是這麼多呢?因為這是可以算出來的,要搞清楚這個問題,我們先從InnoDB索引數據結構、數據組織方式說起。
我們都知道電腦在存儲數據的時候,有最小存儲單元,這就好比我們今天進行現金的流通最小單位是一毛。在電腦中磁碟存儲數據最小單元是扇區,一個扇區的大小是512位元組,而文件系統(例如XFS/EXT4)他的最小單元是塊,一個塊的大小是4k,而對於我們的InnoDB存儲引擎也有自己的最小儲存單元——頁(Page),一個頁的大小是16K。
下麵幾張圖可以幫你理解最小存儲單元:
文件系統中一個文件大小隻有1個位元組,但不得不占磁碟上4KB的空間。

innodb的所有數據文件(尾碼為ibd的文件),他的大小始終都是16384(16k)的整數倍。

磁碟扇區、文件系統、InnoDB存儲引擎都有各自的最小存儲單元。

在MySQL中我們的InnoDB頁的大小預設是16k,當然也可以通過參數設置:

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

數據表中的數據都是存儲在頁中的,所以一個頁中能存儲多少行數據呢?假設一行數據的大小是1k,那麼一個頁可以存放16行這樣的數據。

如果資料庫只按這樣的方式存儲,那麼如何查找數據就成為一個問題,因為我們不知道要查找的數據存在哪個頁中,也不可能把所有的頁遍歷一遍,那樣太慢了。所以人們想了一個辦法,用B+樹的方式組織這些數據。如圖所示:

我們先將數據記錄按主鍵進行排序,分別存放在不同的頁中(為了便於理解我們這裡一個頁中只存放3條記錄,實際情況可以存放很多),除了存放數據的頁以外,還有存放鍵值+指針的頁,如圖中page number=3的頁,該頁存放鍵值和指向數據頁的指針,這樣的頁由N個鍵值+指針組成。當然它也是排好序的。這樣的數據組織形式,我們稱為索引組織表。現在來看下,要查找一條數據,怎麼查?

如select * from user where id=5;

這裡id是主鍵,我們通過這棵B+樹來查找,首先找到根頁,你怎麼知道user表的根頁在哪呢?其實每張表的根頁位置在表空間文件中是固定的,即page number=3的頁(這點我們下文還會進一步證明),找到根頁後通過二分查找法,定位到id=5的數據應該在指針P5指向的頁中,那麼進一步去page number=5的頁中查找,同樣通過二分查詢法即可找到id=5的記錄:
中,那麼進一步去page number=5的頁中查找,同樣通過二分查詢法即可找到id=5的記錄:

5|zhao2|27

現在我們清楚了InnoDB中主鍵索引B+樹是如何組織數據、查詢數據的,我們總結一下:

1、InnoDB存儲引擎的最小存儲單元是頁,頁可以用於存放數據也可以用於存放鍵值+指針,在B+樹中葉子節點存放數據,非葉子節點存放鍵值+指針。

2、索引組織表通過非葉子節點的二分查找法以及指針確定數據在哪個頁中,進而在去數據頁中查找到需要的數據;

那麼回到我們開始的問題,通常一棵B+樹可以存放多少行數據?

這裡我們先假設B+樹高為2,即存在一個根節點和若幹個葉子節點,那麼這棵B+樹的存放總記錄數為:根節點指針數*單個葉子節點記錄行數。

上文我們已經說明單個葉子節點(頁)中的記錄數=16K/1K=16。(這裡假設一行記錄的數據大小為1k,實際上現在很多互聯網業務數據記錄大小通常就是1K左右)。

那麼現在我們需要計算出非葉子節點能存放多少指針,其實這也很好算,我們假設主鍵ID為bigint類型,長度為8位元組,而指針大小在InnoDB源碼中設置為6位元組,這樣一共14位元組,我們一個頁中能存放多少這樣的單元,其實就代表有多少指針,即16384/14=1170。那麼可以算出一棵高度為2的B+樹,能存放1170*16=18720條這樣的數據記錄。

根據同樣的原理我們可以算出一個高度為3的B+樹可以存放:1170117016=21902400條這樣的記錄。所以在InnoDB中B+樹高度一般為1-3層,它就能滿足千萬級的數據存儲。在查找數據時一次頁的查找代表一次IO,所以通過主鍵索引查詢通常只需要1-3次IO操作即可查找到數據。

2. 怎麼得到B+樹的高度?

上面我們通過推斷得出B+樹的高度通常是1-3,下麵我們從另外一個側面證明這個結論。在InnoDB的表空間文件中,約定page number為3的代表主鍵索引的根頁,而在根頁偏移量為64的地方存放了該B+樹的page level。如果page level為1,樹高為2,page level為2,則樹高為3。即B+樹的高度=page level+1;下麵我們將從實際環境中嘗試找到這個page level。

在實際操作之前,你可以通過InnoDB元數據表確認主鍵索引根頁的page number為3,你也可以從《InnoDB存儲引擎》這本書中得到確認。

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;

執行結果:

可以看出資料庫dbt3下的customer表、lineitem表主鍵索引根頁的page number均為3,而其他的二級索引page number為4。關於二級索引與主鍵索引的區別請參考MySQL相關書籍,本文不在此介紹。

下麵我們對資料庫表空間文件做相關的解析:

因為主鍵索引B+樹的根頁在整個表空間文件中的第3個頁開始,所以可以算出它在文件中的偏移量:16384*3=49152(16384為頁大小)。

另外根據《InnoDB存儲引擎》中描述在根頁的64偏移量位置前2個位元組,保存了page level的值,因此我們想要的page level的值在整個文件中的偏移量為:16384*3+64=49152+64=49216,前2個位元組中。

接下來我們用hexdump工具,查看表空間文件指定偏移量上的數據:

linetem表的page level為2,B+樹高度為page level+1=3;

region表的page level為0,B+樹高度為page level+1=1;

customer表的page level為2,B+樹高度為page level+1=3;

這三張表的數據量如下:

總結:

lineitem表的數據行數為600多萬,B+樹高度為3,customer表數據行數只有15萬,B+樹高度也為3。可以看出儘管數據量差異較大,這兩個表樹的高度都是3,換句話說這兩個表通過索引查詢效率並沒有太大差異,因為都只需要做3次IO。那麼如果有一張表行數是一千萬,那麼他的B+樹高度依舊是3,查詢效率仍然不會相差太大。

region表只有5行數據,當然他的B+樹高度為1。

3. 小結

本文從一個問題出發,逐步介紹了InnoDB索引組織表的原理、查詢方式,並結合已有知識,回答該問題,結合實踐來證明。當然為了表述簡單易懂,文中忽略了一些細枝末節,比如一個頁中不可能所有空間都用於存放數據,它還會存放一些少量的其他欄位比如page level,index number等等,另外還有頁的填充因數也導致一個頁不可能全部用於保存數據。關於二級索引數據存取方式可以參考MySQL相關書籍,他的要點是結合主鍵索引進行回表查詢。

來源:cnblogs.com/leefreeman/p/8315844.html
整編:二師兄
關註微信公眾號【悟能之能】瞭解更多編程技巧。


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 借鑒:https://www.cnblogs.com/shijingjing07/p/9301590.html ...
  • u8 key_return = NO_KEY; u8 key_tmp = NO_KEY; u8 key_lock = 0;//按鍵自鎖標誌,自己加的 if (key_val == NO_KEY || key_val != key_ctl.key_val) //按鍵沒有按下或者本次按鍵與上一次按鍵不相 ...
  • 條件判斷: [ condition ],condition前後都有空格 常用的判斷條件: 1)兩個整數的比較 = 字元串比較 -lt 小於 -le 小於等於 -eq 等於 -gt 大於 -ge 大於等於 -ne 不等於 2)按照文件許可權進行判斷 -r有讀的許可權 -w有寫的許可權 -x有執行的許可權 3) ...
  • 一、數據挖掘 中文分詞 • 一段文字不僅僅在於字面上是什麼,還在於怎麼切分和理解。• 例如: – 阿三炒飯店: – 阿三 / 炒飯 / 店 阿三 / 炒 / 飯店• 和英文不同,中文詞之間沒有空格,所以實現中文搜索引擎,比英文多了一項分詞的任務。• 如果沒有中文分詞會出現: – 搜索“達內”,會出現 ...
  • 公司一SQL Server鏡像發生了故障轉移(主備切換),檢查SQL Server鏡像發生主備切換的原因,在錯誤日誌中發現下麵錯誤: Date 2019/8/31 14:09:17 Log SQL Server (Archive #4 - 2019/9/1 0:00:00) Source spid3... ...
  • redis是key-value的數據,所以每個數據都是一個鍵值對。 數據操作的全部命令,可以查看中文網站。 鍵的類型是字元串 值的類型分為五種: 字元串string 哈希hash 列表list 集合set 有序集合zset 字元串string 哈希hash 列表list 集合set 有序集合zset ...
  • 1.獨立模式(standalone|local) nothing! 本地文件系統。 不需要啟用單獨進程。 2.pesudo(偽分佈模式) 等同於完全分散式,只有一個節點。 SSH: //(Socket), //public + private /server : sshd ps -Af | grep ...
  • SELECT select的完整語法: 上述如果都有:執行順序from->where->group by->having->order by->limit->select 列的結果顯示 1、去掉重覆的數據:distinct(針對於記錄而言,不是針對於列的數據而言) 2、運算符:+、-、*、/、%(只 ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發(一):使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說,近來想嘗試開發一款安卓APP,考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP,畢竟是使用Visual Studio開發工具,使用起來也比較的順手,結合微軟官方的教程進行了安卓 ...
  • 前言 QuestPDF 是一個開源 .NET 庫,用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫,它徹底改變了我們生成 PDF 文檔的方 ...
  • 項目地址 項目後端地址: https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址: ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址: http://tree ...
  • 話不多說,直接開乾 一.下載 1.官方鏈接下載: https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe,運行開始下載SQL server; 二. ...
  • 前言 隨著物聯網(IoT)技術的迅猛發展,MQTT(消息隊列遙測傳輸)協議憑藉其輕量級和高效性,已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫,為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog支持多種接收器用於日誌存儲,增強器用於添加屬性,LogContext管理動態屬性,支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項,適用於不同需求。 ...
  • 目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據,爬取信息時需要模擬瀏覽器行為,否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下: 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • 1.前言 什麼是熱更新 游戲或者軟體更新時,無需重新下載客戶端進行安裝,而是在應用程式啟動的情況下,在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR,Xlua,ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles,Addressable, ...
  • 本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺,其實像阿裡雲,騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後,它會送 ...
  • 通過以下方式可以高效,並保證數據同步的可靠性 1.API設計 使用RESTful設計,確保API端點明確,並使用適當的HTTP方法(如POST用於創建,PUT用於更新)。 設計清晰的請求和響應模型,以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證,確保接收到的數據符合預期格 ...