B+树深入探究 | 您所在的位置:网站首页 › 怎样读取指针中的数据 › B+树深入探究 |
1.数据库的读取方式
数据的存储是按照“行”存储的,但是数据库的读取是以“页”的方式。 InnoDB存储引擎就是以“数据页”为单位来进程读写操作的,默认大小为16KB。 下面将按照以下几个部分进行讲解: 2.1数据页的结构
文件头包含两个指针,一个指向上一个数据页,一个指向下一个数据页,连接起来的数据页相当于一个双向链表,这样,数据页不一定需要物理上的连续,只是逻辑上的连续。 数据页中的记录按照“主键”顺序组成单向链表 ->插入和删除记录方便,但是检索效率不高 ->使用页目录提高检索效率 2.2 页目录与记录的关系 可以看到: 1)所有记录包括最小记录与最大记录(但是包含被标记为“已删除”的记录),被划分为几个组。 2)每组的最后一条记录就是组内主键最大的记录,并且该记录的头信息中存储了改组记录有多少条,作为n_owned字段。 3)页目录存储了每组最后一条记录的地址偏移量(槽),他们按照先后顺序存储起来,每个槽相当于指针指向了每组的最后一条记录(也就知道了每组中主键最大的记录)。 4)对于分组中的记录条数有以下规定: a.第一个分组只能有一条记录(最小记录) b.最后一个分组的记录条数范围1 - 8 c.其它分组记录条数4 - 8 这样一来,每次查询某条记录的时候,就可以先采用二分法,将槽指向的记录组的最大记录的主键与查找的记录的主键进行对比,直到查找到记录对应的槽。接着,在该槽对应的记录组中,从头开始查找所要的记录。 3.B+树是如何进行查询的?3.1 B+树的特点 前面讲解的都是一个数据页中记录的组织方式,而现在我们需要考虑数据页之间的组织方式。InnoDB存储引擎采用B+树作为索引,提高了查询性能 可以发现,B+树有如下特点: 1)只有叶子节点才存放了数据,而非叶子节点存放的是目录项(由主键和页编号构成)作为索引 2)非叶子节点通过分层来减少每一层的搜索量 3)所有节点按照索引键大小排序,方便进行范围查询 3.2 B+树查询记录 当查找某条记录的时候,会先根据索引键大小,采用二分法通过非叶子节点的目录项定位到某一数据页,接着在数据页中也是通过二分法定位到某个槽,接着再在该槽所对应的记录组中遍历查找到我们需要的记录。 4.聚集索引与二级索引索引可以分为聚集索引与二级索引,它们的区别在于叶子结点存放的是什么数据,对于聚集索引,叶子结点存放的是完整的用户记录,而二级索引中叶子节点存放的是记录的主键。 InnoDB存储引擎会为每张表创建一个聚集索引,并且由于数据在物理上只有一份,所以聚集索引也只有一个。而二级索引可以有多个。 聚集索引的创建: 1)如果定义了主键,主键作为聚集索引的索引键。 2)如果没有定义主键,选择第一个不包含null值的唯一列作为聚集索引的索引键。 3)如果两个都没有的情况下,InnoDB将会自动生成一个隐式自增的id列作为聚集索引的索引键。 二级索引的结构: 回表与覆盖索引: 回表:查询语句使用了二级索引,那么就会先查询到记录的主键值,然后带着这个主键值再去聚集索引查找该主键对应的完整用户数据。需要查找两次B+树。 覆盖索引:查询语句使用到了二级索引,但是查询的数据是主键值,这个时候在二级索引就能够找到,无需进行回表操作。只需要查找一次B+树。 |
CopyRight 2018-2019 实验室设备网 版权所有 |