先从 MySQL 的基本存储结构说起:
MySQL的基本存储结构是页 (记录都存在页里边) :
各个数据页可以组成一个双向链表
每个数据页中的记录又可以组成一个单向链表:
每个数据页都会为存储在它里边儿的记录生成一个页目录,在通过主键查找某条记录的时候可以在页目录中使用二分法快速定位到对应的槽,然后再遍历该槽对应分组中的记录即可快速找到指定的记录。
所以说,如果我们写
这样没有进行任何优化的sql语句,默认会这样做:
定位到记录所在的页:需要遍历双向链表,找到所在的页
从所在的页内中查找相应的记录:由于不是根据主键查询,只能遍历所在页的单链表了
很明显,在数据量很大的情况下这样查找会很慢!这样的时间复杂度为O(n)。
索引做了些什么可以让我们查询加快速度呢?其实就是将无序的数据变成有序(相对): 要找到id为8的记录简要步骤:
很明显的是:没有用索引我们是需要遍历双向链表来定位对应的页,现在通过 “目录” 就可以很快地定位到对应的页上了!(二分查找,时间复杂度近似为O(logn))
其实底层结构就是B+树,B+树作为树的一种实现,能够让我们很快地查找出对应的记录。
版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。