<返回更多

数据库:innodb数据组织形式

2020-09-09    
加入收藏

MySQL数据库的innodb存储引擎中,数据是按照主键以B+树的形式存储的。如果在建表的时候没有指定主键,那么引擎会自动添加一列主键。

数据库:innodb数据组织形式

B+树

B+树是一种平衡树,即根节点到各个叶子节点的高度不超过1。在B+树中,所有记录节点都是按照键值的大小顺序存在同一层的叶子节点上,由各个叶子节点指针进行链接。B+的形式如上图所示。从上图中,如果用户从最左边的叶子节点遍历即可得到所有键值的顺序排序:4、7、10、15、25、36、50、59、61、65、75、80、85、90。

平时我们常接触的查找结构是平衡二叉树或者红黑树。为什么innodb存储引擎选择了B+树呢?首先我们知道innodb的数据存储磁盘上。由于磁盘IO相对于CPU和内存而言要慢很多,所以减少磁盘IO是提升性能的关键,另外对于机械磁盘而言顺序读取要比随机读取的性能高出1到2个数量级。我们来看上图中的例子,在查找时,可以先将根节点一次读入内存,再进行二分法查找,定位到叶子节点的位置之后,也可以一次将叶子节点加载到内存在进行查找。这样基本上只需要2次IO就能找到数据了。对于平衡二叉树或者红黑树就需要更多次的IO,并且这些IO都是离散读,性能较差。

innodb的主键又被称为聚集索引。通过聚集索引可以直接查找到整条记录(因为B+树的叶子节点就是数据节点,存储了数据)。innodb还有一种辅助索引。这是一个二级索引。它也是B+树组织的,但是叶子节点上的数据,不是数据,而是聚集索引。一个辅助索引的查找的大概过程是:在辅助索引上找到聚集索引,再通过聚集索引找到数据。可以看出相对于聚集索引,辅助索引的查找过程更长,所以一般innodb更倾向于使用聚集索引。但是也有些情况下,查找是搜索辅助索引就能完成。比如:一张表:t(a,b,c),其中a是主键,b是辅助索引,对于select b from t where b > 10或者select count(*) from t where b > 10都是不需要再查找聚集索引的。

我们上面提到了磁盘的顺序读的性能要明显高于随机读。我们再来看辅助索引的查找过程。辅助索引也是B+树组织的,叶子节点是按照辅助索引的值来排序的。这就导致了,如果我们按照辅助索引的顺序去聚集索引查找时,是随机读。innodb为了提升性能,有一种优化,对于辅助索引的范围查找,先找出这些聚集索引,再按照聚集索引进行排序,按照这个顺序去聚集索引中查找,这样可以尽量保证顺序读,并且可以充分利用缓存。

声明:本站部分内容来自互联网,如有版权侵犯或其他问题请与我们联系,我们将立即删除或处理。
▍最近更新
更多资讯 >>>