认识达内从这里开始

认真做教育专心促就业

合肥达内Java培训数据结构类型与应用分析

发布：合肥达内软件培训
来源：互联网
时间：2022-07-20 09:07

数据结构是程序员在学习计算机编程开发技术的时候需要重点掌握的一个编程知识点，而本文我们就通过案例分析来简单了解一下，数据结构类型与应用分析。

合肥达内Java培训数据结构类型与应用分析

BTree指的是BalanceTree，也就是平衡树，平衡树是一颗查找树，并且所有叶子节点位于同一层。

B+Tree是B树的一种变形，它是基于BTree和叶子节点顺序访问指针进行实现，通常用于数据库和操作系统的文件系统中。

B+树有两种类型的节点：内部节点(也称索引节点)和叶子节点，内部节点就是非叶子节点，内部节点不存储数据，只存储索引，数据都存在叶子节点。

内部节点中的key都按照从小到大的顺序排列，对于内部节点中的一个key，左子树中的所有key都小于它，右子树中的key都大于等于它，叶子节点的记录也是按照从小到大排列的。

每个叶子节点都存有相邻叶子节点的指针。

树的常见特性

AVL树

平衡二叉树，一般是用平衡因子差值决定并通过旋转来实现，左右子树树高差不超过1，那么和红黑树比较它是严格的平衡二叉树，平衡条件非常严格(树高差只有1)，只要插入或删除不满足上面的条件就要通过旋转来保持平衡。由于旋转是非常耗费时间的。所以AVL树适用于插入/删除次数比较少，但查找多的场景。

红黑树

通过对从根节点到叶子节点路径上各个节点的颜色进行约束，确保没有一条路径会比其他路径长2倍，因而是近似平衡的。所以相对于严格要求平衡的AVL树来说，它的旋转保持平衡次数较少。适合，查找少，插入/删除次数多的场景。(现在部分场景使用跳表来替换红黑树，可搜索“为啥redis使用跳表(skiplist)而不是使用red-black?”)

B/B+树

多路查找树，出度高，磁盘IO低，一般用于数据库系统中。

B+树与红黑树的比较

红黑树等平衡树也可以用来实现索引，但是文件系统及数据库系统普遍采用B+Tree作为索引结构，主要有以下两个原因：

(一)磁盘IO次数

B+树一个节点可以存储多个元素，相对于红黑树的树高更低，磁盘IO次数更少。

(二)磁盘预读特性

为了减少磁盘I/O操作，磁盘往往不是严格按需读取，而是每次都会预读。预读过程中，磁盘进行顺序读取，顺序读取不需要进行磁盘寻道。每次会读取页的整数倍。

操作系统一般将内存和磁盘分割成固定大小的块，每一块称为一页，内存与磁盘以页为单位交换数据。数据库系统将索引的一个节点的大小设置为页的大小，使得一次I/O就能完全载入一个节点。

【免责声明】：本内容转载于网络，转载目的在于传递信息。文章内容为作者个人意见，本平台对文中陈述、观点保持中立，不对所包含内容的准确性、可靠性与完整性提供形式地保证。请读者仅作参考。更多内容请加danei0707学习了解。欢迎关注“达内在线”参与分销，赚更多好礼。

< 上一篇：合肥达内UI培训UI设计师常用素材收集方法都有哪些

下一篇：合肥达内电脑培训数据库索引类型与应用方法分享 >