文章目录B- 树树--03---B-树、B树、B*树B树是一种树状数据结构它能够存储数据、对其进行排序并允许以O(logn)的时间复杂度进行查找、顺序读取、插入和删除等操作。B树的特性B树---搜索B树---插入分裂的规则是该结点分成两半将中间的关键字进行提升加入到父亲结点中B树---删除B树在磁盘文件中的应用1.磁盘2.磁盘IO局部性原理局部性原理当一个数据被用到时其附近的数据也通常会马上被使用。由于磁盘顺序读取的效率很高不需要寻道时间只需很少的旋转时间因此预读可以提高I/O效率。页文件系统B树B树是对B树的一种变形树特点:B树和B树的差异所以- b树的高度边小了,io寻址效率更高- 存放更多的key- 叶子结点存储了全部数据,且有序,更方便遍历,也更方便区间查找和搜索B 树的优点在于B树的优点在于B树存储数据B树在数据库中的应用Mysql索引---02-索引数据结构未建立主键索引查询建立主键索引查询区间查询B- 树树–03—B-树、B树、B*树前面我们已经学习了二叉查找树、2-3树以及它的实现红黑树。2-3树中一个结点做多能有两个key它的实现红黑树中使用对链接染色的方式去表达这两个key。接下来我们学习另外一种树型结构B树这种数据结构中一个结点允许多于两个key的存在。B树是一种树状数据结构它能够存储数据、对其进行排序并允许以O(logn)的时间复杂度进行查找、顺序读取、插入和删除等操作。B树的特性B树中允许一个结点中包含多个key可以是3个、4个、5个甚至更多并不确定需要看具体的实现。现在我们选择一个参数M来构造一个B树我们可以把它称作是M阶的B树那么该树会具有如下特点每个结点最多有M-1个key并且以升序排列每个结点最多能有M个子结点根结点至少有两个子结点在实际应用中B树的阶数一般都比较大通常大于100所以即使存储大量的数据B树的高度仍然比较小这样在某些应用场景下就可以体现出它的优势。B树—搜索B-树的搜索从根结点开始对结点内的关键字有序序列进行二分查找如果命中则结束否则进入查询关键字所属范围的儿子结点重复直到所对应的儿子指针为空或已经是叶子结点B树—插入新结点一般插在第h层通过搜索找到对应的结点进行插入那么根据即将插入的结点的数量又分为下面几种情况。分裂的规则是该结点分成两半将中间的关键字进行提升加入到父亲结点中如果该结点的关键字个数没有到达m-1个那么直接插入即可如果该结点的关键字个数已经到达了m-1个那么根据B树的性质显然无法满足需要将其进行分裂。分裂的规则是该结点分成两半将中间的关键字进行提升加入到父亲结点中但是这又可能存在父亲结点也满员的情况则不得不向上进行回溯甚至是要对根结点进行分裂那么整棵树都加了一层。其过程如下B树—删除同样的我们需要先通过搜索找到相应的值存在则进行删除需要考虑删除以后的情况B树在磁盘文件中的应用在我们的程序中不可避免的需要通过IO操作文件而我们的文件是存储在磁盘上的。计算机操作磁盘上的文件是通过文件系统进行操作的在文件系统中就使用到了B树这种数据结构。1.磁盘磁盘能够保存大量的数据从GB一直到TB级但是 他的读取速度比较慢因为涉及到机器操作读取速度为毫秒级 。磁盘由盘片构成,每个盘片有两面又称为盘面 。盘片中央有一个可以旋转的主轴他使得盘片以固定的旋转速率旋转通常是5400rpm或者是7200rpm,一个磁盘中包含了多个这样的盘片并封装在一个密封的容器内 。盘片的每个表面是由一组称为磁道同心圆组成的 每个磁道被划分为了一组扇区 每个扇区包含相等数量的数据位通常是512个子节扇区之间由一些间隙隔开,这些间隙中不存储数据 。2.磁盘IO磁盘用磁头来读写存储在盘片表面的位而磁头连接到一个移动臂上移动臂沿着盘片半径前后移动可以将磁头定位到任何磁道上这称之为寻道操作。一旦定位到磁道后盘片转动磁道上的每个位经过磁头时读写磁头就可以感知到该位的值也可以修改值。对磁盘的访问时间分为寻道时间旋转时间以及传送时间。局部性原理局部性原理当一个数据被用到时其附近的数据也通常会马上被使用。由于磁盘顺序读取的效率很高不需要寻道时间只需很少的旋转时间因此预读可以提高I/O效率。由于存储介质的特性磁盘本身存取就比主存慢很多再加上机械运动耗费因此为了提高效率要尽量减少磁盘I/O减少读写操作。 为了达到这个目的磁盘往往不是严格按需读取而是每次都会预读即使只需要一个字节磁盘也会从这个位置开始顺序向后读取一定长度的数据放入内存。这样做的理论依据是计算机科学中著名的局部性原页页是计算机管理存储器的逻辑块硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块每个存储块称为一页1024个字节或其整数倍.预读的长度一般为页的整倍数。主存和磁盘以页为单位交换数据。当程序要读取的数据不在主存中时会触发一个缺页异常此时系统会向磁盘发出读盘信号磁盘会找到数据的起始位置并向后连续读取一页或几页载入内存中然后异常返回程序继续运行。文件系统文件系统的设计者利用了磁盘预读原理将一个结点的大小设为等于一个页1024个字节或其整数倍这样每个结点只需要一次I/O就可以完全载入。那么3层的B树可以容纳102410241024差不多10亿个数据如果换成二叉查找树则需要30层假定操作系统一次读取一个节点并且根节点保留在内存中那么B树在10亿个数据中查找目标值只需要小于3次硬盘读取就可以找到目标值但红黑树需要小于30次因此B树大大提高了IO的操作效率。B树B树是对B树的一种变形树特点:每一个索引旁边会分配一个指针.指针指向下一节点的存储地址信息只有叶子节点的索引元素存储data根节点元素,MySQL运行时一般直接加载进内存.B树和B树的差异非叶结点仅具有索引作用也就是说非叶子结点只存储key不存储value树的所有叶结点构成一个有序链表可以按照key排序的次序遍历全部数据。所以-b树的高度边小了,io寻址效率更高-存放更多的key- 叶子结点存储了全部数据,且有序,更方便遍历,也更方便区间查找和搜索B 树的优点在于由于B树在非叶子结点上不包含真正的数据只当做索引使用因此在内存相同的情况下能够存放更多的key。(树的高度变小了)B树的叶子结点都是相连的因此对整棵树的遍历只需要一次线性遍历叶子结点即可。而且由于数据顺序排列并且相连所以便于区间查找和搜索。—更利于遍历,区间查找和搜索B树的优点在于由于B树的每一个节点都包含key和value因此我们根据key查找value时只需要找到key所在的位置就能找到value但B树只有叶子结点存储数据索引每一次查找都必须一次一次一直找到树的最大深度处也就是叶子结点的深度才能找到value。B树存储数据若参数M选择为5那么每个结点最多包含4个键值对我们以5阶B树为例看看B树的数据存储。B树在数据库中的应用Mysql索引—02-索引数据结构在数据库的操作中查询操作可以说是最频繁的一种操作因此在设计数据库时必须要考虑到查询的效率问题在很多数据库中都是用到了B树来提高查询的效率在操作数据库时我们为了提高查询效率可以基于某张表的某个字段建立索引就可以提高查询效率那其实这个索引就是B树这种数据结构实现的。未建立主键索引查询建立主键索引查询区间查询执行select * from user where id12 and id18,如果有了索引由于B树的叶子结点形成了一个有序链表所以我们只需要找到id为12的叶子结点按照遍历链表的方式顺序往后查即可效率非常高。