MySql教程

浅谈MYSQL的索引以及它的数据结构

本文主要是介绍浅谈MYSQL的索引以及它的数据结构,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

什么是索引

mysql的数据是持久化到磁盘的,写SQL查询数据也就是在磁盘的某个位置查找符合条件的数据,但是磁盘IO比起内存效率是极慢的,特别是数据量大的时候,这时候就需要引入索引来提高查询效率;
在我看来索引是为了提高查询效率而诞生的一种手段,借助合适的数据结构将数据有规律的沉淀下来,使得查询的时候能尽量减少磁盘IO快速返回;也可以类比书本或字典的目录,能快速定位数据

索引的类型

mysql的索引可分为:主键索引(唯一且非空)、唯一索引(可为空)、全文索引、联合索引以及普通索引(普通列做索引)

索引的优点

  • 减少磁盘IO次数,提升查询效率
  • 将随机IO变成顺序IO

索引的数据结构

众所周知,mysql innerDb和myIsam引擎索引的数据结构都是B+树,使用B+树作为索引的数据结构主要是因为相同的磁盘IO次数下B+树的查询表现远高于其他数据结构,并且B+树的叶子节点是收尾相连的,这样更便于顺序查询;下面依次简单介绍下其他数据结构作为索引数据结构的优缺点

HASH表

首先介绍下hash算法,通过hash算法将索引列分散到hash表上去,由于hash是基于内存的,所以效率还是不错的,但是正是因为基于内存导致了其不适合大数据量的计算,浪费内存空间;并且hash算法查询时只有等值计算才会体现他的高效,对于范围查询其还是无能为力;需要注意的是,mysql的memory存储引擎索引的数据结构就是hash表

二叉树

二叉树插入数据时很容易造成树的倾斜,每次插入对应一次IO,效率低下

AVL树

平衡树在二叉树的基础上新增了左旋和右旋,但是需要确保最短子树和最长字树的高度差不大于1;当插入数据量过大时会进行很多次的旋转,导致插入速度极低;查询效率高

红黑树

红黑树相当于是AVL树的一个升级,它通过变色的操作降低了左右旋转的次数,中和了AVL树插入速度慢的缺点;红黑树的要求如下:

  • 任意路径上不能有两个红色节点连续出现
  • 最长子树不超过最短子树的两倍即可
  • 更节点到各子节点的链路中黑色节点的数量一致
    虽说红黑树提高了插入效率,但是受限于一个节点最多只有两个子节点的影响,当数据量大时还是会出现树深度过深从而增加IO次数的问题

B树

B树的每个节点可以有N个节点,这就解决了上面说的树深度的问题,B树的每个节点(包括非叶子节点)不仅会存储页码而且还会存储对应的数据;下面我们分析下B树的查询能力:
mysql是通过磁盘预读来查询数据的,每次可以读取页的整数倍,一页等于4KB,inderDb默认读的是16KB,我们假设一行数据占用1KB的内存并且忽略节点上页面占用的空间,这样三次磁盘IO的话B树能读出161616=4096条数据,效率并不是很理想,并不能满足日常工作中的实际需求

B+树

B+树与B树的区别在于,B+树的非叶子节点不存储数据,数据均存储在叶子节点,且叶子节点收尾相连;我们同样来计算下B+树的查询能力:
由于非叶子节点不存储数据只存储页码,假设一个页码占用10个字节的内存,这样一个磁盘块可以容纳的数据为:(16 * 1000)/10=1600条,假设同样进行三次IO,那么能支持查询的数据量是:1600 * 1600 * 16=40960000,轻松达到千万级别;

这篇关于浅谈MYSQL的索引以及它的数据结构的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!