「成都校区」索引底层数据结构

「成都校区」索引底层数据结构

时间:2020-03-24 06:15 作者:admin 点击:
阅读模式

1.数据库简介

数据库官方描述:是一款用于存储的文件系统 组成部分: 文件系统 + 磁盘 文件系统:文件管理机制 、缓存系统、日志机制、SQL解析器、容灾机制、权限管理、索引模块、锁模块 存储模块:机械硬盘、固态硬盘、磁盘阵列

2.IO的本质 如图是磁盘的平视图 1.黑线:磁头 2.扇区: 磁盘上的每个磁道被等分为若干个弧段,这些弧段便是磁盘的扇区.扇区是磁盘最小的物理存储单元 3.磁道: 以盘片中心为圆心,用不同的半径,划分出不同的很窄的圆环形区域,称为磁道 4.寻道时间:磁头从开始移动到数据所在磁道所需要的时间寻道时间越短,I/O操作越快 5.旋转:盘片彻底旋转到数据加载结束 一次io消耗的时间: 寻道+旋转

3.索引介绍 3.1 什么是索引&&优缺点 索引:是帮助数据库高效获取数据的排好序的数据结构 优势: 1.索引能极大的减少存储引擎需要扫描的数据量 2.索引能将随机io变成顺序io 3.索引能够帮助我们进行分组、排序等操作时,避免使用临时表

劣势: 1.降低更新表的速度,mysql不仅要存储数据,同时还需要保留下一个节点的地址,当改变了索引后,索引树需要 发生改变,保证B+Tree结构完整 2.占用空间 3.2 索引底层的数据结构 索引底层结构通常指的是B+Tree(多路平衡搜索树), 我们平时使用的如 ,聚集索引,复合索引,唯一索引等都默 认使用的是B+TREE,除此以外还有hash索引,或二叉树索引底层结构

3.2.1 平衡二叉查找树 平衡二叉查找树特征 1.树中的每个节点的左子树要小于父节点的值,同时右子数要大于父节点 2.节点的差值不能超过1 3.IO 磁盘次数过多 总结:没有充分和磁盘进行io交互,同时也没有充分利用到局部性原理

3.2.1 多路平衡查找树 3.2.2 B+Tree 区别: 1.B+节点关键字采用闭合区间 2.B+非叶子节点不保存数据相关信息,只保存关键字和子节点的引用 3.B+关键字对 应的数据存在叶子节点上 4.B+树节点是按顺序排列的,相邻节点有顺序引用关系