怎样做企业手机网站首页,加盟凡科建站,四川建设人才网官网,简单大方网站其实平衡二叉树的代码实现已经挺复杂的了#xff0c;但是一山更比一山高#xff0c;B树算法的原理和代码实现都比平衡二叉树要更为复杂。我没有让大家知难而退的意思#xff0c;面试的时候肯定不会让你写B树这么复杂的算法#xff0c;大家先听我讲讲B树这种数据结构的思想吧… 其实平衡二叉树的代码实现已经挺复杂的了但是一山更比一山高B树算法的原理和代码实现都比平衡二叉树要更为复杂。我没有让大家知难而退的意思面试的时候肯定不会让你写B树这么复杂的算法大家先听我讲讲B树这种数据结构的思想吧。一看文章标题就知道B树与文件系统的实现有很大关系这个还是挺重要的。代码实现可能后面我会补上其实意义也不大真的先声明一点B-tree树即B树。B即Balanced平衡因为B树的原英文名称为B-tree而国内很多人喜欢把B-tree译作B-树这是个非常不好的直译很容易让人产生误解人们可能会以为B-树和B树是两种树。B树产生的背景不管是二叉树、二叉查找树还是平衡二叉树它们都有诸多限制比如每个结点只能存储一个元素。结点的度至多为2即使是平衡二叉树在存储百万、千万级别的数据量时也会导致树的深度特别大而深度大就会影响查找效率。这里提一下平衡二叉树的缺点由于平衡二叉树需要左旋和右旋来调整树的结构因此在频繁插入和删除的场景下每插入或删除一个结点都极有可能导致树的不平衡性能也会大打折扣。红黑树(后面会介绍)就是来解决这个问题的。前面讲的几种数据结构都是纯内存操作但是当数据量特别大(如数据库中千万级别的数据表、磁盘中的上万个文件等)内存都存不下了怎么办在这种情况下需要用外存(硬盘)来存储而对数据的处理则需要不断地从硬盘调入调出。此时时间复杂度的计算就会发生变化因为还要额外考虑对硬盘的访问次数和单次访问时间等。为了降低对硬盘的访问次数需要设计新的数据结构。前面讲的几种树结点都只能存一个元素因此当元素非常多的时候要么结点的度非常大要么树的深度非常大这两种情况都会导致对硬盘的访问次数偏大。如果每个结点能存多个元素那么树的总结点数就会大大减少对磁盘的访问次数也会相应的大大减少。由于有如上限制为此引入了多路查找树的概念。多路查找树结点的度可以大于2并且每一个结点可以存储多个元素。由于是查找树所以结点之间存在某种特定的排序关系。B树的基本概念本文要讲的主题是B树B树是一种平衡的多路查找树。其实B树和多路查找树是一个意思网上很多资料也是这样认为的但是也可以认为多路查找树和B树不是一个意思因为多路查找树不一定是平衡的。B树的阶所有结点中的最大孩子数。其实跟树的度一个意思。一个m阶B树的属性如果根结点不是叶子结点则其至少有两颗子树。[m/2]km[m/2]为向上取整比如9阶B树5k9。每一个非根分支结点都有k个孩子和k-1个元素叶子结点有k-1个元素。所有叶子结点在同一层(平衡)。所有分支结点有下列信息数据(n,A0,K1,A1,K2,A2,...,Kn,An)n是结点存储的元素个数Ai表示子树Ki表示元素而从A0到An的值是从小到大排序的这跟二叉查找树的性质一样。下面来演示一下如何在B树上查找元素如下图是一颗B树。如果要查找元素7首先从硬盘上读取根节点(第一次读磁盘)即读到了3,5,8三个元素发现7并不在其中但由于578因此找到了A2然后根据A2再读取一次硬盘(第二次读磁盘)此时读到了2,6,7三个元素找到了元素7两次磁盘读取就查找了我们想要的元素非常高效B树就是这样一种为内外存数据交互为设计的数据结构。本文介绍了B树产生的背景和基本概念下一篇文章将介绍B树结点的插入和删除操作以及后面将陆续介绍B树、红黑树等。
