1.索引数据结构红黑树,Hash,B+树详解
索引的本质
描述:索引是帮助Mysql高效获取数据的排好序的数据结构
索引数据结构分类
1.二叉树
特点:左边小右边大于等于父节点
缺点:如果插入自增长索引,一直单边增长,对查询没有意义,如下图
2.红黑树
特点:自动保持平衡
缺点:楼层太高,查询次数过多,维护复杂
3.Hash表
特点:对索引值进行hash运算,得到磁盘文件指针,查询where index=1的等值预算的时候性能非常高
缺点:空间能力差,做范围查询where index>1的时候不好做索引
4.B-Tree
叶节点具有相同的深度,叶节点的指针为空
所有索引元素不重复
节点中的数据索引从左到右递增排列
对比:比红黑树楼层低,查询效率高
缺点:每个索引对应一个值,导致索引占用空间太大
B+Tree(MySql底层采用B+Tree数据结构)
特点:非叶子节点不存储data,只存储索引(冗余),可以放更多的索引
叶子节点包含所有索引字段
叶子节点用指针连接,提高区间访问的性能
2.索引是怎么支撑千万级表的快速查找
一个索引(8B)加上一个指针(6B),mysql允许最大值为16kb,16kb/(6B+8B)=1170个分叉,所以最后结果为1170*1170*16=21902400两千多万
3.面试常问B+树索引面试题解析
Mysql存储引擎:
1.MyISAM(非聚集索引)
文件:.frm 存储数据结构 .MYD存储数据记录.MYI存储索引
查询方式:根据索引查找内存空间指针,再根据空间指针再MYD文件查找记录
2.InnerDB(聚集索引)
文件:.frm 存储数据结构 .idb数据和索引存在一起
查询方式:根据索引直接查找数据
提问:聚集索引和非聚集索引区别
答:非聚集索引是通过空间指正查找MYD文件查询到的数据,聚集索引是因为索引和数据存储在一起,每一条记录前面都有个索引,可以直接通过索引取数据
提问:为什么InnoDB表必须有主键,并且推荐使用整型的自增主键?
答:InnoDB就是这样设计的,通过主键索引构建B+Tree;整形比较大小比字符串比较大小更快更高效,例如比较1<2比a>b更高效,字符串比较还要转换asci,自增是不用打破原来的B+Tree,直接再后面加数据,如果不是,可能需要重新元素分裂平衡
提问:为什么非主键索引结构叶子节点存储的是主键值?
答:一致性和节省存储空间,所有的非主键索引最后定位到的是主键索引,然后再通过主键索引查找数据,换而言之,就是差了两次树,非主键索引定位到主键索引,这样节省了存储空间,如果建了多个非主键索引,我就要保存多个记录,如果非主键索引做了修改,主键索引没有,这样就导致了数据不一致,但是如果非主键索引最后定位到主键索引,通过主键索引查找数据,这样就保持了一致性
4.联合索引底层数据结构又是怎样的
和主键索引类似,不过是有多个字段组成