InnoDB索引的原理

在鵝廠后端開發一面，我遇到了如題這樣一個比較寬泛的問題，當時可能只是背了相關概念，對于索引的了解不是很深刻。
最近，我花了很大的功夫去深入了解MySQL的索引。
下面是我的一些思考：
索引，對于InnoDB來說，索引通常是指一棵B+樹（聚簇索引或二級索引）。

  • 對于聚簇索引來說，只是葉子節點存放的列包括主鍵和其他列，索引存放的是每個頁中最小主鍵值和頁號
  • 對于非聚簇索引來說，葉子節點存放的是 索引列 和主鍵值，非葉子節點存放的是最小主鍵值和頁號+ 索引列的值(保證在B+樹的同一層內節點的目錄項記錄除頁號這個字段以外是唯一的)

原因是：InnoDB的B+樹索引是有序的。對于復合索引（比如索引列a,b），如果有多條記錄a,b值相同，InnoDB需要依靠主鍵值來唯一定位和排序。下面舉一個具體的例子說明：

假設 數據庫建表語句如下：

mysql> CREATE TABLE index_demo(-> c1 INT,-> c2 INT,-> c3 CHAR(1),-> PRIMARY KEY(c1)-> INDEX idx_c2 (c2)-> ) ROW_FORMAT = Compact;

主鍵是C1, 二級索引C2，假設表中的數據是
在這里插入圖片描述
如果二級索引中目錄項記錄的內容只是 索引列 + 頁號 的搭配的話，那么為 c2 列建立索引后的 B+ 樹應該長這樣
在這里插入圖片描述
如果我們想新插入一行記錄，其中 c1 、 c2 、 c3 的值分別是： 9 、 1 、 ‘c’ ，那么在修改這個為 c2 列建立的二級索引對應的 B+ 樹時便碰到了個大問題：由于 頁3 中存儲的目錄項記錄是由 c2列 + 頁號 的值構成的，頁3 中的兩條目錄項記錄對應的 c2 列的值都是 1 ，而我們新插入的這條記錄的 c2 列的值也是 1 ，那我們這條新插入的記錄到底應該放到 頁4 中，還是應該放到 頁5 中啊？答案是：無法判斷。

為了讓新插入記錄能找到自己在那個頁里，我們需要保證在B+樹的同一層內節點的目錄項記錄除 頁號 這個字段以外是唯一的。所以對于二級索引的內節點的目錄項記錄的內容實際上是由三個部分構成的：

  • 索引列的值
  • 主鍵值
  • 頁號

也就是我們把 主鍵值 也添加到二級索引內節點中的目錄項記錄了，這樣就能保證 B+ 樹每一層節點中各條目錄項記錄除 頁號 這個字段外是唯一的，所以我們為 c2 列建立二級索引后的示意圖實際上應該是這樣子的
在這里插入圖片描述
這樣我們再插入記錄 (9, 1, ‘c’) 時，由于 頁3 中存儲的目錄項記錄是由 c2列 + 主鍵 + 頁號 的值構成的，可
以先把新記錄的 c2 列的值和 頁3 中各目錄項記錄的 c2 列的值作比較，如果 c2 列的值相同的話，可以接著比較
主鍵值，因為 B+ 樹同一層中不同目錄項記錄的 c2列 + 主鍵 的值肯定是不一樣的，所以最后肯定能定位唯一的
一條目錄項記錄，在本例中最后確定新記錄應該被插入到 頁5 中。

索引同層的非葉子結點間，是否也用雙線鏈表維系呢？

是的，如果詢問AI 大模型，大部分都是回答沒有，這顯然是錯誤的，為此我查閱了相關Mysql 源碼的實現storage/innobase/include/fil0fil.h 的第461 行

#define FIL_PAGE_PREV		8	/*!< 如果頁面存在一個“自然”的前驅頁面，則記錄其偏移量。否則，該字段為FIL_NULL。對于BLOB頁面，此字段未設置，因為BLOB頁面是以單鏈表形式存儲的。另請參見FIL_PAGE_NEXT。 */#define FIL_PAGE_NEXT		12	/*!< 如果存在頁面的“自然”后繼節點，則記錄其偏移量。否則為FIL_NULL。相同PAGE_LEVEL的B樹索引頁（FIL_PAGE_TYPE包含FIL_PAGE_INDEX）通過FIL_PAGE_PREV和FIL_PAGE_NEXT按照每頁上最小用戶記錄的排序順序維護為雙向鏈表。 */

相同PAGE_LEVEL的B樹索引頁,（FIL_PAGE_TYPE包含FIL_PAGE_INDEX）,通過FIL_PAGE_PREV和FIL_PAGE_NEXT,按照每頁上最小用戶記錄的排序順序,維護為雙向鏈表。

非葉子結點各層的雙向鏈表，連起來起了什么作用呢？

深入了解 源碼后，在storage/innobase/btr/btr0btr.cc 中找到了相關的代碼實現

  1. 支持范圍掃描操作
// 在進行范圍掃描時會使用這些鏈接:
if (left_page_no != FIL_NULL) {prev_block = btr_block_get(page_id_t(space, left_page_no), block->page.size,RW_X_LATCH, index, mtr);
}if (next_page_no != FIL_NULL) {next_block = btr_block_get(page_id_t(space, next_page_no), block->page.size,RW_X_LATCH, index, mtr);
}
  1. 維護B樹結構的完整性
// 在頁面分裂時需要維護這些鏈接關系:
btr_page_set_next(lower_page, lower_page_zip, upper_page_no, mtr);
btr_page_set_prev(upper_page, upper_page_zip, lower_page_no, mtr);if (direction != FSP_DOWN) {btr_page_set_next(upper_page, upper_page_zip, next_page_no, mtr);
}
  1. 優化查詢性能
// 在查詢時可以快速定位到相鄰頁面:
static
void
btr_cur_prefetch_siblings(buf_block_t*    block)
{page_t* page = buf_block_get_frame(block);ulint left_page_no = fil_page_get_prev(page);ulint right_page_no = fil_page_get_next(page);// 預讀相鄰頁面以提高性能if (left_page_no != FIL_NULL) {buf_read_page_background(...);}if (right_page_no != FIL_NULL) {buf_read_page_background(...);}
}
  1. 支持頁面合并操作
// 在刪除操作導致頁面需要合并時:
void
btr_discard_page(btr_cur_t*  cursor,mtr_t*      mtr)
{// 獲取相鄰頁面號left_page_no = btr_page_get_prev(buf_block_get_frame(block), mtr);right_page_no = btr_page_get_next(buf_block_get_frame(block), mtr);if (left_page_no != FIL_NULL) {// 與左側頁面合并merge_block = btr_block_get(...);}
}
  1. 數據一致性檢查
// 在驗證索引時會檢查相鄰頁面的記錄順序:
if (!dict_index_is_spatial(index)&& cmp_rec_rec(rec, right_rec,offsets, offsets2, index, false) >= 0) {// 如果相鄰頁面的記錄順序不正確,報錯btr_validate_report2(index, level, block, right_block);
}

每個頁對應一個目錄項，每個目錄項包括下邊兩個部分：

聚簇索引

在這里插入圖片描述

  • 頁的用戶記錄中最小的主鍵值，我們用 key 來表示。
  • 頁號，我們用page_no 表示。

聚簇索引是一種特殊的B+ 樹

滿足以下 兩個特點：

  1. 使用記錄主鍵值的大小進行記錄和頁的排序，這包括三個方面的含義
    • 頁內的記錄是按照主鍵的大小順序排成一個單向鏈表。
    • 各個存放用戶記錄的頁也是根據頁中用戶記錄的主鍵大小順序排成一個雙向鏈表。
    • 存放目錄項記錄的頁分為不同的層次，在同一層次中的頁也是根據頁中目錄項記錄的主鍵大小順序排成一個雙向鏈表。
  2. B+ 樹的葉子節點存儲的是完整的用戶記錄。
    所謂完整的用戶記錄，就是指這個記錄中存儲了所有列的值（包括隱藏列）

之前我們說過索引的構造和用戶記錄頁 很相似，那么InnoDB 怎么區分一條記錄是普通的用戶記錄還是目錄項記錄呢？別忘了記錄頭信息里的record_type 屬性，它的各個取值代表的意思如下：

  • 0 ：普通的用戶記錄
  • 1 ：目錄項記錄
  • 2 ：最小記錄
  • 3 ：最大記錄

參考：《從根上理解MySQL》

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/web/78215.shtml
繁體地址，請注明出處：http://hk.pswp.cn/web/78215.shtml
英文地址，請注明出處：http://en.pswp.cn/web/78215.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！

相關文章

FormCalc 支持的編程語言和軟件

FormCalc 支持的編程語言和軟件

FormCalc 是一種專為 PDF 表單計算設計的腳本語言&#xff0c;主要應用于 Adobe 生態及 SAP 相關工具。以下是支持 FormCalc 的主要軟件和平臺&#xff1a; 1. Adobe LiveCycle Designer&#xff08;最佳支持&#xff09; 原生支持&#xff1a;FormCalc 是 LiveCycle Designe…
閱讀更多...
unity 為什么不切片 Sprite.rect 與Sprite.textureRect的值還不一樣

unity 為什么不切片 Sprite.rect 與Sprite.textureRect的值還不一樣

一。測試代碼&#xff1a; 二。發現Debug不一樣的原因 與解決方案&#xff1a; 下圖右邊所示&#xff1a; 網格類型默認為緊密 在 Unity 中&#xff0c;紋理導入時可能存在自動的偏移和裁剪設置。即便你沒有手動切片&#xff0c;Unity 可能會根據紋理的導入設置&#xff0c;對…
閱讀更多...
超預期！淘寶閃購提前開放全國全量，聯合餓了么扭轉外賣戰局

超預期！淘寶閃購提前開放全國全量，聯合餓了么扭轉外賣戰局

餓了么由守轉攻。 作者|景行 編輯|楊舟 淘寶餓了么&#xff0c;終于落子&#xff0c;“淘寶閃購”&#xff0c;橫空出世&#xff0c;僅僅2天&#xff0c;業務加速。 4月30日上午&#xff0c;當外賣戰場陷入沉寂時&#xff0c;淘寶宣布將即時零售業務“小時達”升級為“淘寶閃…
閱讀更多...
minio相關面試問題和參考答案

minio相關面試問題和參考答案

可以考慮以下幾個方面&#xff1a; MinIO概述與特性MinIO與其他對象存儲的比較MinIO的使用場景MinIO的API與SDKMinIO的安全性與權限管理MinIO的性能優化 以下是一些相關的面試技術問題及其參考回答&#xff1a;具體如下&#xff1a; MinIO的主要特性包括&#xff1a; 高性能&am…
閱讀更多...
加載ko驅動模塊：顯示Arm版本問題解決！

加載ko驅動模塊：顯示Arm版本問題解決！

1、問題 驅動模塊加載&#xff0c;使用命令&#xff1a;modprobe chrdevbase.ko 時出現&#xff1a; hrdevbase: version magic 4.1.15 SMP preempt mod_unload modversions ARMv6 p2v8 ’ should be 4.1.15 SMP preempt mod_unload modversions ARMv7 p2v8 ’ ———————…
閱讀更多...
【論文閱讀一】掌握高效閱讀法，開啟學術研究新旅程：S. Keshav教授論文閱讀的三遍法

【論文閱讀一】掌握高效閱讀法，開啟學術研究新旅程：S. Keshav教授論文閱讀的三遍法

文章目錄 一、三遍閱讀法1. 初讀&#xff1a;10分鐘&#xff1a;宏觀把握&#xff0c;快速篩選2. 第二遍&#xff1a;1個小時&#xff1a;更仔細的閱讀&#xff0c;了解文中論點3. 第三遍&#xff1a;深入理解&#xff0c;注重細節&#xff0c;挑戰假設 二、運用三遍閱讀法進行…
閱讀更多...
3D Gaussian Splatting部分原理介紹和CUDA代碼解讀

3D Gaussian Splatting部分原理介紹和CUDA代碼解讀

本系列旨在幫助無CUDA代碼經驗的讀者、以及3DGS的初學者理解代碼邏輯。 3D GS論文原文鏈接&#xff1a;https://arxiv.org/abs/2308.04079 論文筆記鏈接&#xff1a;【論文筆記】3D Gaussian Splatting for Real-Time Radiance Field Rendering 【論文筆記】A Survey on 3D Ga…
閱讀更多...
【數據結構】--- 雙向鏈表的增刪查改

【數據結構】--- 雙向鏈表的增刪查改

前言&#xff1a; 經過了幾個月的漫長歲月&#xff0c;回頭時年邁的小編發現&#xff0c;數據結構的內容還沒有寫博客&#xff0c;于是小編趕緊停下手頭的活動&#xff0c;補上博客以洗清身上的罪孽 目錄 前言&#xff1a; 概念&#xff1a; 雙鏈表的初始化 雙鏈表的判空 雙鏈表…
閱讀更多...
Ubuntu如何查看硬盤的使用情況，以及掛載情況。

Ubuntu如何查看硬盤的使用情況，以及掛載情況。

在Ubuntu中查看硬盤使用情況及掛載情況&#xff0c;可通過以下命令實現&#xff1a; 一、查看硬盤使用情況 df -h 顯示所有掛載文件系統的磁盤空間使用情況&#xff08;含總容量、已用空間、可用空間等&#xff09;&#xff0c;輸出結果以易讀格式&#xff08;如GB、MB&#x…
閱讀更多...
Github 2025-05-02Java開源項目日報 Top9

Github 2025-05-02Java開源項目日報 Top9

根據Github Trendings的統計，今日(2025-05-02統計)共有9個項目上榜。根據開發語言中項目的數量，匯總情況如下： 開發語言項目數量Java項目9Android開源輕量級流媒體前端 創建周期：3158 天開發語言：Java協議類型：GNU General Public License v3.0Star數量：28641 個Fork數量…
閱讀更多...
linux學習——數據庫API創建

linux學習——數據庫API創建

一.API操作 1.int sqlite3_open(char *filename,sqlite3 **db) 功能&#xff1a;打開sqlite數據庫 參數&#xff1a; filename:數據庫文件路徑 db:指向sqlite句柄的指針 &#xff08;splite3* db;&#xff09; 返回值…
閱讀更多...
Baklib內容中臺落地實戰指南

Baklib內容中臺落地實戰指南

內容中臺實施最佳路徑 在構建企業級內容中臺的實踐中&#xff0c;架構設計與流程優化構成核心支撐框架。通過四庫體系&#xff08;知識庫、資源庫、模板庫、場景庫&#xff09;的有機組合&#xff0c;企業可實現從知識沉淀到場景化應用的閉環管理。智能檢索技術結合語義分析引…
閱讀更多...
【重走C++學習之路】26、類型轉換

【重走C++學習之路】26、類型轉換

目錄 一、C語言中的類型轉換 二、C中的四個類型轉換 2.1 static_cast 2.2 dynamic_cast 2.3 const_cast 2.4 reinterpret_cast 2.5 總結 結語 一、C語言中的類型轉換 在C語言中&#xff0c;如果賦值運算符左右兩側類型不同&#xff0c;或者形參與實參類型不匹配&a…
閱讀更多...
kotlin 過濾 filter 函數的作用和使用場景

kotlin 過濾 filter 函數的作用和使用場景

1. filter 函數的作用 filter 是 Kotlin 集合操作中的一個高階函數&#xff0c;用于根據指定條件從集合中篩選出符合條件的元素。 作用&#xff1a;遍歷集合中的每個元素&#xff0c;并通過給定的 lambda 表達式判斷是否保留該元素。返回值&#xff1a;一個新的集合&#xff…
閱讀更多...
安卓程序打包與發布

安卓程序打包與發布

一 配置編譯信息 二 創建密鑰
閱讀更多...
LeetCode算法題 （移除鏈表元素）Day15！！！C/C++

LeetCode算法題 （移除鏈表元素）Day15！！！C/C++

https://leetcode.cn/problems/remove-linked-list-elements/description/ 一、題目分析 給你一個鏈表的頭節點 head 和一個整數 val &#xff0c;請你刪除鏈表中所有滿足 Node.val val 的節點&#xff0c;并返回 新的頭節點 。 今天的題目非常好理解&#xff0c;也就是要刪除…
閱讀更多...
Scrapy框架之【Scrapy-Redis】分布式爬蟲詳解

Scrapy框架之【Scrapy-Redis】分布式爬蟲詳解

Scrapy-Redis 介紹 Scrapy-Redis 是一個基于 Redis 實現的 Scrapy 分布式爬蟲組件。Scrapy 本身是一個強大的 Python爬蟲框架&#xff0c;但它默認是單進程單線程的&#xff0c;在面對大規模數據抓取任務時效率不高。Scrapy-Redis 則解決了這一問題&#xff0c;它允許你將 Scra…
閱讀更多...
Gradio全解20——Streaming：流式傳輸的多媒體應用（3）——實時語音識別技術

Gradio全解20——Streaming：流式傳輸的多媒體應用（3）——實時語音識別技術

Gradio全解20——Streaming&#xff1a;流式傳輸的多媒體應用&#xff08;3&#xff09;——實時語音識別技術 本篇摘要20. Streaming&#xff1a;流式傳輸的多媒體應用20.3 實時語音識別技術20.3.1 環境準備和開發步驟1. 環境準備2. ASR應用開發步驟&#xff08;基于Transform…
閱讀更多...
使用xlwings將兩張順序錯亂的表格進行數據核對

使用xlwings將兩張順序錯亂的表格進行數據核對

有如下一個excel表&#xff0c;姓名列的內容相同&#xff0c;順序不同&#xff1b;月薪有部分內容不同。 目的&#xff1a;要找出哪幾條月薪不同。 通常的做法&#xff0c;要使用excel的高級篩選。 在此&#xff0c;使用xlwings實現&#xff0c;在不同的內容上涂色。 代碼如…
閱讀更多...
2025大模型安全研究十大框架合集（10份）

2025大模型安全研究十大框架合集（10份）

2025大模型安全研究十大框架合集的詳細介紹&#xff1a; Anthropic AI信任研究框架 Anthropic于2024年10月更新的《安全責任擴展政策》(RSP)&#xff0c;提出了一個靈活的動態AI風險治理框架。該框架規定當AI模型達到特定能力時&#xff0c;將自動升級安全措施&#xff0c;如…
閱讀更多...
最新文章

Copyright @ 2022~2023