深入理解Mysql索引底层数据结构与算法

索引是帮助MySQL高效获取数据的排好序的数据结构

1.常见的数据结构讲解

1.1 二叉树

1.1.1 二叉树的定义

二叉树（binary tree）是指树中节点的度不大于2的有序树，它是一种最简单且最重要的树。二叉树的递归定义为：二叉树是一棵空树，或者是一棵由一个根节点和两棵互不相交的，分别称作根的左子树和右子树组成的非空树；左子树和右子树又同样都是二叉树

1.1.2 二叉树示例

非叶子结点的左边指向小于其关键字的子树，右边指向大于其关键字的子树

上图我在查找6的时候需要进行6次查询 才能找到6 元素

1.1.3 Mysql为什么不使用二叉树进行数据存储

在存储过程中二叉树 可能会蜕变成链表的形式 如1.1.2 图示例 此时查找数据就几乎和全表扫描没有区别 就使得当前的二叉树变得不平衡 那么要想满足查询效率 就需要在数据插入的时候进行二叉树的平衡 很显然这个效率是低下的 这就是mysql 为什么没有使用二叉树来做索引的数据结构存储

1.2 红黑树

1.2.1 红黑树的定义

红黑树实则是对二叉树的一个优化 会自动平衡也叫（二叉平衡树） 其中每个节点都带有颜色属性（通常是红色或黑色）。这种树的自平衡性质使得红黑树在插入和删除操作时能够保持比较好的性能。

1.2.2 红黑树示例

1.2.3 Mysql 为什么不适用红黑树进行数据存储

随着数据的增多，红黑树的高度会越来越高 当我需要查找一个叶子节点需要进行查找的次数会变得很多 在树的高度不可控的情况下 随着数据的增多树的高度会变高 效率也就会变低

1.3 Hash表

1.4 B-Tree

1.4.1 B-Tree的定义

B-Tree 是一种自平衡的树形数据结构也是人们常说中的B树 ，用于存储数据并保证数据的快速检索

B树的特点在于它的节点可以拥有多个子节点，并且每个节点可以拥有多个关键字，这使得B树可以存储大量的数据。B树的节点被设计成可以存储多个关键字和指向子节点的指针，这使得B树可以在一个节点中存储更多的关键字，从而减少了树的深度和查找次数。

节点中的数据索引从左到右递增排列

1.4.2 B-Tree示例

1.4.3 Mysql为何不适用B-Tree

B-Tree没有内部节点和叶子结点的区分，它的每个节点都是即存了key又存了data，由于没有内部节点和叶子结点的区分，使得B树没有将叶子结点用链表串联起来的结构。
因为B树不管叶子节点还是非叶子节点，都会保存数据，这样导致在非叶子节点中能保存的指针数量变少，指针少的情况下要保存大量数据，只能增加树的高度，导致IO操作变多，查询性能变低。

1.5 B+Tree

1.5.1 B+Tree的定义

用于高效地存储和检索数据。它是一种平衡树，其中每个节点都有多个子节点。B+树是一种多叉树，它的特点是每个节点都有多个子节点和多个关键字，并且每个关键字都对应一个指针，指向子节点中的某一个。

• 非叶子节点不存储数据，只存储索引，可以存放更多的索引
• 叶子节点包含所有索引字段
• 叶子节点用指针连接，提高区间访问的性能
• 节点中的数据从左到右依次递增

1.5.2 B+Tree 示例

查看mysql文件页大小（16K）：SHOW GLOBAL STATUS like 'Innodb_page_size'