二叉树:
一个根节点,每个节点下挂着最多2个子节点。、
概念:
度:结点的分支数,二叉树度为2。
深度:树的层次。
二叉排序树:
二叉树的基础上,每个节点上都有一个数字,节点上的数字都比右节点上的大。
应用场景:
基于内存的排序数据结构,写入时将数据写入到对应的位置。数据可能会出现倾斜,可以想到数字写入顺序如果不是50-20-60-18-55,而是18-20-50-55-60,那么二叉树就会退变为链表。
B-树:
B-树每个节点上包含着数据和指针,每个指针指向其一个子节点的位置,并且数据的个数为指针的2d-1个。这里的d是指针的个数,同时也是树的“度”。
B-树的查找需要一次对每个节点进行二分查找,直至找到或返回null。通常,可以引入布朗过滤器等方式加速查找。
B-树的写入、删除时要进行分裂、合并、转移等操作,越是非顺序的插入就越容易碰到这些高性能消耗的操作。
应用场景:
一般B-树常常作为磁盘的查找的数据结构使用。
一般磁盘为了减少寻道时间,往往会进行预读,一次读入1个或多个page的数据。我们只要将B-树的每个节点控制在一个page大小,就可以保证,磁盘一次的查找只需要一次IO。一个page大小一般在4k,可以存储不少的数据,假设一个节点存储数据量为100,深度为3的B-树,即可保存100w数据量(100*100*100),而100的数据一般用不了4k的存储空间。
当然,这里节点中存储的东西主要包括data和指针,指针大小是固定的,而数据有大有小。只要控制好每个数据块的大小,就可以提高B-树的性能。
另外,一般情况下非叶子节点占用空间一般较小,上面的例子中,非叶子节点数据量只有1w,完全可以缓存至内存中,这点也是在实际数据库实现中常常使用到的优化。
B+树:
B+树完全是对B-树的工程级优化,非叶子节点不在存储data,只有根节点才存储数据。最大程度的加大了单个page中指针的个数,增加数的度。减少了树的层次。
另外相比较于B-树,其key的个数变为指针个数的2d个。
应用场景:
实际在数据库系统中使用时,往往每个叶子节点都会存储一个其相邻节点的一个指针,用来在范围查找时有更好的性能。
- 大小: 9.2 KB
- 大小: 18 KB
- 大小: 22.5 KB
分享到:
相关推荐
树的存储结构、森林及与二叉树的转换树的存储结构、森林及与二叉树的转换
B树数据存储结构介绍 看完就就明白了。在此分享
mySql实现树形查询的函数存储过程例子
本主要是树状数据(多叉树)在数据库中存储的示例源码,同时包含数据表的设计示例,满满的代码干货
空间栅格数据由于冗余度高,数据相关性强,直接存储会造成存储空间的浪费,而利用Huffman树生成的Huffman编码是一种非定长编码,能够将出现频率较高的像元灰度值编译为较短的编码,从而实现空间栅格数据的无损压缩。...
第1关求图(邻接矩阵存储)最小生成树的普里姆(Prim)算法 第2关求图(邻接表存储)最小生成树的普里姆(Prim)算法 第3关求图(邻接矩阵存储)最小生成树的克鲁斯卡尔(Kruskal)算法 第4关求图(邻接表存储)最小...
编写程序,实现求采用链式存储结构存储的二叉树的树高
C语言树据结构 抽象数据类型的实现—树 利用二叉链表的存储结构,开发工具:VC++
使用C++模板实现了,基于顺序存储的泛型多叉树容器, 其中包括前序、后序、兄弟、叶子、深度5种迭代器的实现,方便了多叉树的遍历。
用二叉链表作存储结构。 要求: (1)以回车('\n')为输入结束标志,输入数列L,生成一棵二叉排序树T; (2)对二叉排序树T作中序遍历,输出结果; (3)计算二叉排序树T查找成功的平均查找长度,输出结果; (4)输入元素x,...
基于B+树的简易数据库存储系统c++源码.zip基于B+树的简易数据库存储系统c++源码.zip基于B+树的简易数据库存储系统c++源码.zip基于B+树的简易数据库存储系统c++源码.zip基于B+树的简易数据库存储系统c++源码.zip基于B...
B+树实现,利用文件在硬盘上存储,具体使用说明在文档中
注:非网上流传的“一种理想的在关系数据库中存储树型结构数据的方法”。 该存储算法对查询,插入,移动,删除均显得高效,当然也有一定的局限性,读者自己分析。
严蔚敏版对应树的基础结构 初学数据结构 数的构造 利用c语言
但是咱们有面对这样一个实际问题:就是大规模数据存储中,实现索引查询这样一个实际背景下,树节点存储的元素数量是有限的(如果元素数量非常多的话,查找就退化成节点内部的线性查找了),这样导致二叉查找树结构...
统计利用二叉树存储的森林中树的棵数.cpp
此时采用三叉树链表储存二叉树。 其中,data,lchild,rchild三个域的含义同二叉树,parent域为指向该结点的双亲结点指针。 5.4.4 线索链表 按照某种遍历次序对二叉树进行遍历,可以把二叉树中所有结点排成一个线性...
赫夫曼树和赫夫曼编码的存储表示,自己搞定的,关键是一些总结。一些风格和数学的重要性,程序风格如HT[s1].parent=HT[s2].parent = i就淫荡的不行了,要分行在VC6下才能运行,数学也很重要,一些纠结的问题的时候,...
分布式存储技能图谱,较为全面的分布式存储技能学习路线。 建域本人接触分布式存储系统中的ceph开源分布式存储较多,所以关于具体的分布式系统主要偏向于ceph的技能; 除此之外,其他的技能基本是一个好得分布式...