Mysql学习笔记------索引

索引内容比较多,一次性学不完就分批记录吧.
说起优化sql,很多人第一反应就是添加索引,那索引到底是什么,为什么能优化sql? 这也是我学习索引的目的.

概念: 索引是协助快速查询,更新数据库表中数据的有序的数据结构.

Mysql的数据模型:
这也是我今天学习的重点,我一直认为想对一项技术了解的更深入,不妨从它为什么被创造,解决了哪些问题开始了解.

先从有序数组,链表结构说起,这两种结构是我们常见的.
有序数组,如ArrayList,特点是查找快,增删慢,链表结构,如LinkedLisr,特点是增删快,查找慢,相信很多人都背过这个.

ArrayList为什么查询快呢? 因为它可以通过索引快速定位元素位置,从而查找出来.
而针对大量数据查找,如何快速定位数据位置呢?相信很多人都知道,就是二分法.

因此有了二叉查找树模型
二叉查找树: 特点是左子树的节点 < 父节点,右子树的节点 > 父节点,这样一来需要查询的索引值大于父节点时我直接从右子树开始查询即可,实现快速查找.但二叉查找树存在一个问题,当所有数据都比父节点大(小)时,树结构会只有右(左)侧,导致树结构不平衡,看起来像链表结构,这样一来,查找起来依然很慢了.

为了解决斜树的问题,所以有了平衡二叉树(AVL树)

平衡二叉树(AVL树): 特点是左右子树深度差绝对值不能超过1,当两侧深度绝对值 大于1时,会进行旋转操作,将中间值提升为父节点.

每个节点存储了键值,数据磁盘地址以及子节点的引用.

平衡二叉树也存在一些问题,每个节点存储的数据较少,而每访问一次树节点会进行一次I/O操作,而节点数据较少的情况下I/O的效率是非常低的,更不幸的是如果查询的数据在最深的节点,I/O操作非常频繁,既浪费了空间也浪费了效率.

上述问题依然有解决方案,就是多路平衡查找树(BTree)

多路平衡查找树(Btree): 每个节点可以拥有多个键值及子树,子树数量叫做度,将空间利用更大化,同时因为空间的压缩,树的深度也会减少,I/O操作也会降低很多.

而Mysql使用的数据模型则是BTree的升级版,B+Tree.
B+tree:

从图中可以看到几点:
关键字数等于度数,只有叶子节点会存储数据,且叶子节点之间数据有序排列,同时还有指针指向下一节点,形成链表结构.

在区间查询时,当查询完第一次后无需重新回到父节点再次查询,可以直接通过叶子节点的有序链表查询后面的数据,因此I/O操作更少一些,同时更加稳定.

今日学习就这么多,明天再更新.