検索

本篇介绍下MySQL的InnoDB索引相关知识,从各种树到索引原理到存储的细节。InnoDB是MySQL的默认存储引擎(MySQL5.5.5之前是MyISAM,

摘要:

本篇介绍下MySQL的InnoDB索引相关知识,从各种树到索引原理到存储的细节。

InnoDB是MySQL的默认存储引擎(MySQL5.5.5之前是MyISAM,)。本着高效学习的目的,本篇以介绍InnoDB为主,少量涉及MyISAM作为对比。

这篇文章是我在学习过程中总结完成的,内容主要来自书本和博客(参考文献会给出),过程中加入了一些自己的理解,描述不准确的地方烦请指出。

1 各种树形结构

本来不打算从二叉搜索树开始,因为网上已经有太多相关文章,但是考虑到清晰的图示对理解问题有很大帮助,也为了保证文章完整性,,最后还是加上了这部分。

先看看几种树形结构:

1 搜索二叉树:每个节点有两个子节点,数据量的增大必然导致高度的快速增加,显然这个不适合作为大量数据存储的基础结构。

2 B树:一棵m阶B树是一棵平衡的m路搜索树。最重要的性质是每个非根节点所包含的关键字个数 j 满足:┌m/2┐ - 1

3 B+树:一棵m阶B树是一棵平衡的m路搜索树。最重要的性质是每个非根节点所包含的关键字个数 j 满足:┌m/2┐ - 1

4 B*树:一棵m阶B树是一棵平衡的m路搜索树。最重要的两个性质是1每个非根节点所包含的关键字个数 j 满足:┌m2/3┐ - 1

B/B+/B*三种树有相似的操作,比如检索/插入/删除节点。这里只重点关注插入节点的情况,且只分析他们在当前节点已满情况下的插入操作,因为这个动作稍微复杂且能充分体现几种树的差异。与之对比的是检索节点比较容易实现,而删除节点只要完成与插入相反的过程即可(在实际应用中删除并不是插入的完全逆操作,往往只删除数据而保留下空间为后续使用)。

先看B树的分裂,下图的红色值即为每次新插入的节点。每当一个节点满后,就需要发生分裂(分裂是一个递归过程,参考下面7的插入导致了两层分裂),由于B树的非叶子节点同样保存了键值,所以已满节点分裂后的值将分布在三个地方:1原节点,2原节点的父节点,3原节点的新建兄弟节点(参考5,7的插入过程)。分裂有可能导致树的高度增加(参考3,7的插入过程),也可能不影响树的高度(参考5,6的插入过程)。

MySQL的InnoDB索引详细分析

B+树的分裂:当一个结点满时,分配一个新的结点,并将原结点中1/2的数据复制到新结点,最后在父结点中增加新结点的指针;B+树的分裂只影响原结点和父结点,而不会影响兄弟结点,所以它不需要指向兄弟节点的指针。

MySQL的InnoDB索引详细分析

B*树的分裂:当一个结点满时,如果它的下一个兄弟结点未满,那么将一部分数据移到兄弟结点中,再在原结点插入关键字,最后修改父结点中兄弟结点的关键字(因为兄弟结点的关键字范围改变了)。如果兄弟也满了,则在原结点与兄弟结点之间增加新结点,并各复制1/3的数据到新结点,最后在父结点增加新结点的指针。可以看到B*树的分裂非常巧妙,因为B*树要保证分裂后的节点还要2/3满,如果采用B+树的方法,只是简单的将已满的节点一分为二,会导致每个节点只有1/2满,这不满足B*树的要求了。所以B*树采取的策略是在本节点满后,继续插入兄弟节点(这也是为什么B*树需要在非叶子节点加一个兄弟间的链表),直到把兄弟节点也塞满,然后拉上兄弟节点一起凑份子,自己和兄弟节点各出资1/3成立新节点,这样的结果是3个节点刚好是2/3满,达到B*树的要求,皆大欢喜。

MySQL的InnoDB索引详细分析

B+树适合作为数据库的基础结构,完全是因为计算机的内存-机械硬盘两层存储结构。内存可以完成快速的随机访问(随机访问即给出任意一个地址,要求返回这个地址存储的数据)但是容量较小。而硬盘的随机访问要经过机械动作(1磁头移动 2盘片转动),访问效率比内存低几个数量级,但是硬盘容量较大。典型的数据库容量大大超过可用内存大小,这就决定了在B+树中检索一条数据很可能要借助几次磁盘IO操作来完成。如下图所示:通常向下读取一个节点的动作可能会是一次磁盘IO操作,不过非叶节点通常会在初始阶段载入内存以加快访问速度。同时为提高在节点间横向遍历速度,真实数据库中可能会将图中蓝色的CPU计算/内存读取优化成二叉搜索树(InnoDB中的page directory机制)。

真实数据库中的B+树应该是非常扁平的,可以通过向表中顺序插入足够数据的方式来验证InnoDB中的B+树到底有多扁平。我们通过如下图的CREATE语句建立一个只有简单字段的测试表,然后不断添加数据来填充这个表。通过下图的统计数据(来源见参考文献1)可以分析出几个直观的结论,这几个结论宏观的展现了数据库里B+树的尺度。

MySQL InnoDB存储引擎锁机制实验

InnoDB存储引擎的启动、关闭与恢复

MySQL InnoDB独立表空间的配置

MySQL Server 层和 InnoDB 引擎层 体系结构图

InnoDB 死锁案例解析

MySQL Innodb独立表空间的配置

1 每个叶子节点存储了468行数据,每个非叶子节点存储了大约1200个键值,这是一棵平衡的1200路搜索树!

2 对于一个22.1G容量的表,也只需要高度为3的B+树就能存储了,这个容量大概能满足很多应用的需要了。如果把高度增大到4,则B+树的存储容量立刻增大到25.9T之巨!

3 对于一个22.1G容量的表,B+树的高度是3,如果要把非叶节点全部加载到内存也只需要少于18.8M的内存(如何得出的这个结论?因为对于高度为2的树,1203个叶子节点也只需要18.8M空间,而22.1G从良表的高度是3,非叶节点1204个。同时我们假设叶子节点的尺寸是大于非叶节点的,因为叶子节点存储了行数据而非叶节点只有键和少量数据。),只使用如此少的内存就可以保证只需要一次磁盘IO操作就检索出所需的数据,效率是非常之高的。

更多详情见请继续阅读下一页的精彩内容:  

linux

声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。
MySQLのパフォーマンスを監視するために使用できるツールは何ですか?MySQLのパフォーマンスを監視するために使用できるツールは何ですか?Apr 23, 2025 am 12:21 AM

MySQLのパフォーマンスを効果的に監視する方法は? MySqladmin、ShowGlobalStatus、PerconAmonitoring and Management(PMM)、MySQL EnterpriseMonitorなどのツールを使用します。 1. mysqladminを使用して、接続の数を表示します。 2。showglobalstatusを使用して、クエリ番号を表示します。 3.PMMは、詳細なパフォーマンスデータとグラフィカルインターフェイスを提供します。 4.mysqlenterprisemonitorは、豊富な監視機能とアラームメカニズムを提供します。

MySQLはSQL Serverとどのように違いますか?MySQLはSQL Serverとどのように違いますか?Apr 23, 2025 am 12:20 AM

MySQLとSQLServerの違いは次のとおりです。1)MySQLはオープンソースであり、Webおよび埋め込みシステムに適しています。2)SQLServerはMicrosoftの商用製品であり、エンタープライズレベルのアプリケーションに適しています。ストレージエンジン、パフォーマンスの最適化、アプリケーションシナリオの2つには大きな違いがあります。選択するときは、プロジェクトのサイズと将来のスケーラビリティを考慮する必要があります。

どのシナリオでMySQLよりもSQL Serverを選択できますか?どのシナリオでMySQLよりもSQL Serverを選択できますか?Apr 23, 2025 am 12:20 AM

高可用性、高度なセキュリティ、優れた統合を必要とするエンタープライズレベルのアプリケーションシナリオでは、MySQLの代わりにSQLServerを選択する必要があります。 1)SQLServerは、高可用性や高度なセキュリティなどのエンタープライズレベルの機能を提供します。 2)VisualStudioやPowerbiなどのMicrosoftエコシステムと密接に統合されています。 3)SQLSERVERは、パフォーマンスの最適化に優れた機能を果たし、メモリが最適化されたテーブルと列ストレージインデックスをサポートします。

MySQLは文字セットと照合をどのように処理しますか?MySQLは文字セットと照合をどのように処理しますか?Apr 23, 2025 am 12:19 AM

mysqlManagesCharacterSetSetSetsAndCollat​​ions ByUSINGUTF-8ASTHEDEDEFAULT、CONFIGURATIONATDATABASE、TABLE、ANDCOLUMNLEVELS、ANDREQUIRINGCAREACTERSETANDCOLLATIONSFORADABASE.2

mysqlのトリガーとは何ですか?mysqlのトリガーとは何ですか?Apr 23, 2025 am 12:11 AM

MySQLトリガーは、特定のデータ操作が実行されたときに一連の操作を実行するために使用されるテーブルに関連付けられた自動的に実行されたストアドプロシージャです。 1)定義と機能のトリガー:データ検証、ロギングなどに使用。2)動作原則:それは前後に分割され、行レベルのトリガーをサポートします。 3)使用例:給与の変更を記録したり、在庫を更新したりするために使用できます。 4)デバッグスキル:ShowTriggersとShowCreatetriggerコマンドを使用します。 5)パフォーマンスの最適化:複雑な操作を避け、インデックスを使用し、トランザクションを管理します。

MySQLでユーザーアカウントをどのように作成および管理しますか?MySQLでユーザーアカウントをどのように作成および管理しますか?Apr 22, 2025 pm 06:05 PM

MySQLでユーザーアカウントを作成および管理する手順は次のとおりです。1。ユーザーの作成:createUser'newuser '@' localhost'identifidedby'password 'を使用します。 2。許可を割り当てる:grantselect、insert、updateonmydatabase.to'newuser'@'localhost 'を使用します。 3.許可エラーを修正:Revokeallprivilegesonmydatabase.from'newuser'@'localhost 'を使用します。次に、許可を再割り当てします。 4。最適化権限:Showgraを使用します

MySQLはOracleとどのように違いますか?MySQLはOracleとどのように違いますか?Apr 22, 2025 pm 05:57 PM

MySQLは、迅速な開発や中小規模のアプリケーションに適していますが、Oracleは大規模な企業や高可用性のニーズに適しています。 1)MySQLはオープンソースで使いやすく、Webアプリケーションや中小企業に適しています。 2)Oracleは強力で、大企業や政府機関に適しています。 3)MySQLはさまざまなストレージエンジンをサポートし、Oracleは豊富なエンタープライズレベルの機能を提供します。

他のリレーショナルデータベースと比較してMySQLを使用することの欠点は何ですか?他のリレーショナルデータベースと比較してMySQLを使用することの欠点は何ですか?Apr 22, 2025 pm 05:49 PM

他のリレーショナルデータベースと比較したMySQLの欠点には次のものがあります。1。パフォーマンスの問題:大規模なデータを処理する際にボトルネックに遭遇する可能性があり、PostgreSQLは複雑なクエリとビッグデータ処理でより良いパフォーマンスを発揮します。 2。スケーラビリティ:水平スケーリング能力は、Google SpannerやAmazon Auroraほど良くありません。 3。機能的な制限:高度な機能におけるPostgreSQLやOracleほど良くないため、一部の関数では、より多くのカスタムコードとメンテナンスが必要です。

See all articles

ホットAIツール

Undresser.AI Undress

Undresser.AI Undress

リアルなヌード写真を作成する AI 搭載アプリ

AI Clothes Remover

AI Clothes Remover

写真から衣服を削除するオンライン AI ツール。

Undress AI Tool

Undress AI Tool

脱衣画像を無料で

Clothoff.io

Clothoff.io

AI衣類リムーバー

Video Face Swap

Video Face Swap

完全無料の AI 顔交換ツールを使用して、あらゆるビデオの顔を簡単に交換できます。

ホットツール

ZendStudio 13.5.1 Mac

ZendStudio 13.5.1 Mac

強力な PHP 統合開発環境

SAP NetWeaver Server Adapter for Eclipse

SAP NetWeaver Server Adapter for Eclipse

Eclipse を SAP NetWeaver アプリケーション サーバーと統合します。

DVWA

DVWA

Damn Vulnerable Web App (DVWA) は、非常に脆弱な PHP/MySQL Web アプリケーションです。その主な目的は、セキュリティ専門家が法的環境でスキルとツールをテストするのに役立ち、Web 開発者が Web アプリケーションを保護するプロセスをより深く理解できるようにし、教師/生徒が教室環境で Web アプリケーションを教え/学習できるようにすることです。安全。 DVWA の目標は、シンプルでわかりやすいインターフェイスを通じて、さまざまな難易度で最も一般的な Web 脆弱性のいくつかを実践することです。このソフトウェアは、

VSCode Windows 64 ビットのダウンロード

VSCode Windows 64 ビットのダウンロード

Microsoft によって発売された無料で強力な IDE エディター

SublimeText3 Mac版

SublimeText3 Mac版

神レベルのコード編集ソフト(SublimeText3)