MySQL索引学习

MySQL索引学习

 MySQL官方对索引的定义为:索引是帮助MySQL高效获取数据的数据结构。

索引的本质:索引是数据结构,可以简单的理解为“排好序的快速查找B+树数据结构”

B+树:B代表平衡(balance)而不是二叉(binary)

检索原理:

MySQL索引学习

 mysql索引结构:

BTREE

B树(Balance Tree多路平衡查找树)

B+树(加强版多路平衡查找树)

为什么是B+树?

通过六步迭代演变:

1.全部遍历

2.Hash

找一次就能找到,而不是遍历,保证一次性。hash搞不定范围和排序查找。

加速查找速度的数据结构,常见的有两类:

(1)哈希,例如hashmap,查询/插入/修改/删除的平均时间复杂度都是O(1);

(2)树,例如平衡二叉搜索树,查询/插入/修改/删除的平均时间复杂度都是O(log2(n));

可以看到,不管是读请求,还是写请求,哈希类型的索引,都要比树型的索引更快一些,那为什么,索引结构要设计成树型呢?

想想范围/排序等其他sql条件:

哈希型的索引,时间复杂度会退化为O(n),而树型的“有序”特性,依然能保持O(log2(n))的高效率。

备注:InnoDB并不支持哈希索引。O(n)指查找n次。

3.二叉树

哈希比树快,索引结构为什么要设计成树型?

MySQL索引学习

 普通二叉树存在两种问题:

MySQL索引学习

出现左倾或右倾问题

 MySQL索引学习

 又是链表又是树

4.平衡二叉树(AVL)

 从算法的数学逻辑来讲,二叉树的查找速度和比较次数都是最小的,那为什么选择BTREE?

只要是平衡二叉树,随着树的增加,根节点会变化,不会变左倾错误。

MySQL索引学习

比如10,查找次数是4。如果数据量越多,树就会越高,查找次数就越多。数据量越多,树就会越高,遍历的次数就会越多,IO就会开销越大,导致系统性能下降。

遗留问题:树高问题导致磁盘IO过多。尽量从瘦高变矮胖。

5.B树

MySQL索引学习

底层原理:

MySQL索引学习

 磁盘页/块:

sql说话:

MySQL索引学习

块/页关系:

 MySQL索引学习

B树检索原理:

MySQL索引学习

 MySQL索引学习

 总结:B树比平衡二叉树少了一次IO操作

6.B+树:

 MySQL索引学习

 MySQL索引学习

 检索原理

 MySQL索引学习

 MySQL索引学习

B+树与B树的区别:

非叶子节点只存储键值信息

所有叶子节点之间都有一个链指针

数据记录都存放在叶子节点中

相关推荐