沈阳网站推广的公司,培训网站模板,做高清视频的网站,豫icp郑州网站建设文章目录 一、B树1.B树的概念2.B树的特性3.B树的插入的过程4.总结 二、B*树1. B*树的概念2.B*树的分裂 三、总结四、B树系列和哈希和平衡搜索树作对比五、B树的一些应用1.索引2.MySQL索引3.MyISAM2.InnoDB 一、B树
1.B树的概念 B树是B树的变形#xff0c;是在B树基础上优化的… 文章目录 一、B树1.B树的概念2.B树的特性3.B树的插入的过程4.总结 二、B*树1. B*树的概念2.B*树的分裂 三、总结四、B树系列和哈希和平衡搜索树作对比五、B树的一些应用1.索引2.MySQL索引3.MyISAM2.InnoDB 一、B树
1.B树的概念 B树是B树的变形是在B树基础上优化的多路平衡搜索树B树的规则跟B树基本类似但是又在B树的基础上做了以下几点改进优化 分支节点的子树指针与关键字个数相同 分支节点的子树指针p[i]指向关键字值大小在[k[i]k[i1])区间之间。相当于取消了最左边的那棵树 所有叶子节点增加一个链接指针链接在一起 所有关键字及其映射数据都在叶子节点出现 分支结点跟叶子结点有重复的值分支结点存的是叶子结点的索引。父亲中存的是孩子结点中的最小值做索引 2.B树的特性 B树的特性 所有关键字都出现在叶子节点的链表中且链表中的节点都是有序的。不可能在分支节点中命中。分支节点相当于是叶子节点的索引叶子节点才是存储数据的数据层 3.B树的插入的过程
如下是M3时候的B树的插入分裂过程 B树的插入过程根B树是类似的细节区别在于第一次插入两层一层结点做分支一层做根 后面一样都是往叶子中去插入的插入满了以后分裂一半给兄弟转换成往父亲插入一个key和一个孩子孩子就是兄弟key是兄弟的第一个最小的key。 B树的分裂 当一个结点满时分配一个新的结点并将原结点中1/2的数据复制到新结点最后在父结点中增加新结点的指针B树的分裂只影响原结点和父结点而不会影响兄弟结点所以它不需要指向兄弟的指针。 4.总结 简化了B树孩子比关键字多一个的规则变成了相等所有的值都在叶子上方便遍历查找所有的值 二、B*树
1. B*树的概念 B*树是B树的变形在B树的非根和非叶子节点再增加指向兄弟节点的指针 2.B*树的分裂 B树的分裂 当一个结点满时分配一个新的结点并将原结点中1/2的数据复制到新结点最后在父结点中增加新结点的指针B树的分裂只影响原结点和父结点而不会影响兄弟结点所以它不需要指向兄弟的指针。 B*树的分裂 当一个结点满时如果它的下一个兄弟结点未满那么将一部分数据移到兄弟结点中再在原结点插入关键字最后修改父结点中兄弟结点的关键字因为兄弟结点的关键字范围改变了如果兄弟也满了则在原结点与兄弟结点之间增加新结点并各复制1/3的数据到新结点最后在父结点增加新结点的指针。 所以B*树分配新结点的概率比B树要低空间使用率更高 B*的结点的关键字和和孩子数量是在[2/3*M, M]之间的 三、总结 大致将B树B树B*树总结如下 B树有序数组平衡多叉树 B树有序数组链表平衡多叉树 B*树一棵更丰满的空间利用率更高的B树。 四、B树系列和哈希和平衡搜索树作对比
在内存中作内查找时候 单纯论树的高度搜索效率B树确实不错 但是B树系列也有一些隐形坏处 空间利用率低消耗高 插入删除数据时分裂和合并节点那么必然挪动数据 虽然高度更低但是在内存中而言与哈希和平衡搜索树还是一个量级中。 比如当M为1024的时候N为10亿的时候 B树的次数为3次而平衡树的效率为30次 在内存中搜索3次和30次差别不是特别大 但是在磁盘中搜索3次和30次差别巨大 结论实质上B树系列在内存中体现不出优势
五、B树的一些应用
1.索引 **B-树最常见的应用就是用来做索引。**索引通俗的说就是为了方便用户快速找到所寻之物比如书籍目录可以让读者快速找到相关信息hao123网页导航网站为了让用户能够快速的找到有价值的分类网站本质上就是互联网页面中的索引结构 MySQL官方对索引的定义为索引(index)是帮助MySQL高效获取数据的数据结构简单来说索引就是数据结构 当数据量很大时为了能够方便管理数据提高数据查询的效率一般都会选择将数据保存到数据库因此数据库不仅仅是帮助用户管理数据而且数据库系统还维护着满足特定查找算法的数据结构这些数据结构以某种方式引用数据这样就可以在这些数据结构上实现高级查找算法该数据结构就是索引。 像我们在使用B树去索引磁盘数据的时候分支结点只存储key值这就可以使得分支结点比较小。分支结点映射的磁盘数据块就可以尽量加载到Cache中从而提高效率 2.MySQL索引 mysql是目前非常流行的开源关系型数据库不仅是免费的可靠性高速度也比较快而且拥有灵活的插件式存储引擎 MySQL中索引属于存储引擎级别的概念不同存储引擎对索引的实现方式是不同的。 注意索引是基于表的而不是基于数据库的 3.MyISAM MyISAM引擎是MySQL5.5.8版本之前默认的存储引擎不支持事务支持全文检索使用BTree作为索引结构叶节点的data域存放的是数据记录的地址其结构如下 上图是以以Col1为主键MyISAM的示意图可以看出MyISAM的索引文件仅仅保存数据记录的地址。在MyISAM中主索引和辅助索引Secondary key在结构上没有任何区别只是主索引要求key是唯一的而辅助索引的key可以重复。如果想在Col2上建立一个辅助索引则此索引的结构如下图所示 同样也是一棵BTreedata域保存数据记录的地址。因此MyISAM中索引检索的算法为首先按照BTree搜索算法搜索索引如果指定的Key存在则取出其data域的值然后以data域的值为地址读取相应数据记录。MyISAM的索引方式也叫做“非聚集索引”的。 我们也可以用name来进行索引。 一般数据库要求主键是唯一的比如mysql建表的主键就是Bs树的key。B树的value是存储一行数据的磁盘地址 分支节点也是需要存盘中的因为数据量大了内存是存不下的分支结点中应该是磁盘地址。 但是分支结点理论上应该被尽量缓存到cache 一般数据库要求主键值是不重复唯一字段比如电话、身份证号码适合但是名字地址不适合 没有字段能保持唯一可以考虑自增主键其实它自己建立一个自增整数做完主键 一般数据库不要求索引唯一像mysql建立索引可以考虑使用B树或者Hash表数据结构允许冗余 像下面的语句中插入第二条语句就会报错因为主键张伟已经存在了。 B树做主键索引相比B树的优势如下 B树所有值都在叶子遍历很方便方便区间查找对于没有建立索引的字段全表扫描的遍历很方便分支结点值存储key一个分支结点空间占用更小可以尽可能加载到缓存 B树不用叶子就能找到值B树一定要到叶子这是B树一个优势但是B树高度足够低所以差别不大 2.InnoDB InnoDB存储引擎支持事务其设计目标主要面向在线事务处理的应用从MySQL数据库5.5.8版本开始InnoDB存储引擎是默认的存储引擎。InnoDB支持B树索引、全文索引、哈希索引。但InnoDB使用BTree作为索引结构时具体实现方式却与MyISAM截然不同。 第一个区别是InnoDB的数据文件本身就是索引文件。MyISAM索引文件和数据文件是分离的索引文件仅保存数据记录的地址。而InnoDB索引表数据文件本身就是按BTree组织的一个索引结构这棵树的叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键因此InnoDB表数据文件本身就是主索引。 上图是InnoDB主索引同时也是数据文件的示意图可以看到叶节点包含了完整的数据记录这种索引叫做聚集索引。因为InnoDB的数据文件本身要按主键聚集所以InnoDB要求表必须有主键MyISAM可以没有如果没有显式指定则MySQL系统会自动选择一个可以唯一标识数据记录的列作为主键如果不存在这种列则MySQL自动为InnoDB表生成一个隐含字段作为主键这个字段长度为6个字节类型为长整型 第二个区别是InnoDB的辅助索引data域存储相应记录主键的值而不是地址,所有辅助索引都引用主键作为data域 聚集索引这种实现方式使得按主键的搜索十分高效但是辅助索引搜索需要检索两遍索引首先检索辅助索引获得主键然后用主键到主索引中检索获得记录。
