MySQL索引学习
MySQL官方对索引的定义为:索引是帮助MySQL高效获取数据的数据结构。
索引的本质:索引是数据结构,可以简单的理解为“排好序的快速查找B+树数据结构”
B+树:B代表平衡(balance)而不是二叉(binary)
检索原理:
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.二叉树
哈希比树快,索引结构为什么要设计成树型?
普通二叉树存在两种问题:
出现左倾或右倾问题
又是链表又是树
4.平衡二叉树(AVL)
从算法的数学逻辑来讲,二叉树的查找速度和比较次数都是最小的,那为什么选择BTREE?
只要是平衡二叉树,随着树的增加,根节点会变化,不会变左倾错误。
比如10,查找次数是4。如果数据量越多,树就会越高,查找次数就越多。数据量越多,树就会越高,遍历的次数就会越多,IO就会开销越大,导致系统性能下降。
遗留问题:树高问题导致磁盘IO过多。尽量从瘦高变矮胖。
5.B树
底层原理:
磁盘页/块:
sql说话:
块/页关系:
B树检索原理:
总结:B树比平衡二叉树少了一次IO操作
6.B+树:
检索原理
B+树与B树的区别:
非叶子节点只存储键值信息
所有叶子节点之间都有一个链指针
数据记录都存放在叶子节点中