问题

mysql之索引原理

题库小秘书

发表于 2019-03-13 19:07:47

索引宗旨:   减少查询范围,无序变为有序
mysql  b+树索引支持范围查找和最左匹配查找
磁盘IO的性能开销远大于内存IO,  每次查找数据时把磁盘IO次数控制在一个很小的数量级,最好是常数数量级。
多路搜索树:  每个节点有N个元素,和N+1个孩子,尽量减少树的高度,减少磁盘IO次数

IO次数取决于B+树的高度

索引字段要尽量的小:通过上面的分析,我们知道IO次数取决于b+数的高度h,假设当前数据表的数据为N,每个磁盘块的数据项的数量是m,则有h=㏒(m+1)N,当数据量N一定的情况下,m越大,h越小;

而m = 磁盘块的大小 / 数据项的大小,磁盘块的大小也就是一个数据页的大小,是固定的,如果数据项占的空间越小,数据项的数量越多,树的高度越低。这就是为什么每个数据项,即索引字段要尽量的小,比如int占4字节,要比bigint8字节少一半。这也是为什么b+树要求把真实的数据放到叶子节点而不是内层节点,一旦放到内层节点,磁盘块的数据项会大幅度下降,导致树增高。当数据项等于1时将会退化成线性表。

因为每次磁盘IO,  寻址到每一页数据量是4k-8k, 如果索引字段越小,磁盘块的数据项就会越多。
磁盘读取数据是以磁盘块为基本单位,

 

B+树
B树的变种;
分支结点只存索引,不存具体数据;
叶子结点包含所有数据,并且包含叶子结点本身按着关键字大小自小而大顺序连接;

B+-tree 的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对B 树更小。如果把所有同一内部结点的关键字存放在同一盘块中,那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说IO读写次数也就降低了。