什么是Mysql索引 Mysql索引的定义和作用

什么是Mysql索引

今天介绍什么是Mysql索引的相关知识，接下来IT袋网小编就来介绍。

思考:了解过索引吗？（什么是索引）

索引（index）: 帮助MySQL高效获取数据的数据结构(有序)。

在数据之外，数据库系统还维护着满足特定查找算法的数据结构（B+树），这些数据结构以某种方式引用（指向）数据， 这样就可以在这些数据结构上实现高级查找算法，这种数据结构就是索引

思考:Mysql索引的底层数据结构了解过嘛?

MySQL默认使用的索引底层数据结构是B+树

再介绍B+树之前，我们先知道二叉树(主要是二叉搜索树和红黑树)和B树

1.二叉树

二叉树: 顾名思义，每个节点最多有两个“叉”，也就是两个子节点，分别是左子节点和右子节点。不过，二叉树并不要求每个节点都有两个子节点，有的节点只有左子节点，有的节点只有右子节点。二叉树每个节点的左子树和右子树也分别满足二叉树的定义

常见的二叉树有:

• 满二叉树
• 完全二叉树
• 二叉搜索树
• 红黑树

1.1. 二叉搜索树

二叉搜索树(Binary Search Tree,BST)：名二叉查找树，有序二叉树或者排序二叉树，是二叉树中比较常用的一种类型

二叉查找树要求，在树中的任意一个节点，其左子树中的每个节点的值，都要小于这个节点的值，而右子树节点的值都大于这个节点的值

在极端情况下，二叉树会形成一个单向链表，结构如下：

二叉搜索树,属于最坏的情况，已经退化成了链表，左右子树极度不平衡，此时查找的时间复杂度肯定是O(n)

1.2. 二叉树作为索引结构缺点

• 1.如果数据是有序的，则会顺序插入，形成链表，查询效率就降低
• 2.如果数据量比较大，层级就比较深，检索效率就慢

2. 红黑树

考虑到二叉树有这些缺点后，我们可能就会考虑使用二叉树进阶版红黑树，红黑树是一个自由平衡二叉树，解决了是顺序插入数据形成单向链表的缺点，最终形成的数据结构也是一颗平衡的二叉树

红黑树（Red Black Tree）：也是一种自平衡的二叉搜索树(BST)，之前叫做平衡二叉B树（Symmetric Binary B-Tree）

红黑树数据结构如下: