Innodb索引数据结构灵魂拷问
问题1:Innodb数据结构为什么要用B+树,如果比红黑树要好的话,为什么Java HashMap不用B+树而用红黑树?
用B+树是因为查询快和稳定。Innodb的数据组织在一个聚集索引上,默认是主键聚集索引,叶子节点存放完整数据,非叶子节点存放索引数据。由于非叶子节点只存储索引,一页就能存更多的数据。内存与磁盘进行交互是以页作为单位的,每页的数据越多,就能减少与磁盘交互的次数。所以就能提升查询的速度。因为数据都在叶子节点,所以查找的路径是一样长的。所以查询时间会很稳定。
如果数据全在内存的话,红黑树要比B+树好,查找次数比B+树要少很多,B+树适合磁盘IO,因为一次IO可以加载很多节点数据,查找次数虽多但IO次数少。红黑树是瘦长的,B+树是矮胖的。IO的次数取决于树的高度,另外红黑树也不够平衡。
问题2:为什么IO的次数要取决于树的高度,我一次IO多加载几层不一样可以少些IO吗,必须得一层层加载到内存?
因为Innodb是把一页的数据放在同一高度的,一次IO加载一页,只能一层层加载,就是这么设计的,然后在这个设计基础上,当然是每层的数据填满页,即把树变胖,高度变矮IO次数会更少。
问题3:为什么不用二叉查找树?
随着数据不断变化,二叉查找树会倾斜,退化成一个线性结构,跟链表一样。问题4:为什么不用B树?
因为B树的非叶子节点也不光有索引的Key还有Data,那一次IO加载的一页数据16K中的索引Key就要少很多,那这势必要更多次IO才能加载出所需的索引Key了。所以应该把非叶子节点的Data去掉,把空间让给索引Key。另外每个节点都存储具体数据也使得查询变得不稳定,有些是查到第一层就找到了,有些要找到最后一层。
问题5:为什么默认不用Hash索引?
仅支持=,in查询。
索引冲突多的话,相同hash的数据是链表的线性结构,查找起来也不快。
问题6:为什么建议InnoDB表必须建主键,并且推荐使用整型的自增主键?
1.为什么要有主键?
如果不建主键,MySQL会帮我们选一个非空唯一列来当主键组织聚簇索引,如果没有则建一个隐藏列rowid当主键。这就强加了一些工作给MySQL,没必要。并且如果选择出来的非整型自增字段作主键性能也不好。
2.为什么要整型?
查找时比较大小更快
3.为什么要自增?
避免插入时增加维护聚簇索引的开销。
如果使用自增主键:
那么每次插入新的记录,记录就会顺序添加到当前索引节点的后续位置,主键的顺序按照数据记录的插入顺序排列,自动有序。当一页写满,就会自动开辟一个新的页。
如果使用非自增主键(如身份证号或学号等):
由于每次插入主键的值近似于随机,因此每次新纪录都要被插到现有索引页得中间某个位置,此时MySQL不得不为了将新记录插到合适位置而移动数据,甚至目标页面可能已经被回写到磁盘上而从缓存中清掉,此时又要从磁盘上读回来,这增加了很多开销,同时频繁的移动、分页操作造成了大量的碎片,得到了不够紧凑的索引结构,后续不得不通过OPTIMIZE TABLE来重建表并优化填充页面。
以上总结自互联网
2023/10/04 23:15