欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

一些树的结构备忘 数据结构CC++C# 

程序员文章站 2022-07-15 12:53:23
...
B+ tree
ISAM tree
AVL(平衡树)
二叉树

二叉树对上面几个有用的东西是中序遍历

AVL的定义是各个节点其左右节点的高度相差不超过1.实现时,每个节点中会含有一个该节点高度的字段来存放这个信息.
insert操作后的重新平衡策略:
1.如果新建立的节点是w,则从w开始向上遍历,找这样第一个x,x的爷爷是不平衡的节点z,x的父亲就是y.
2.将x y z按其中序遍历的序列重新命名成 a b c
3. 将a和c放到b下面,将a b c原来的子树放到a 和 c下面,同时修改各层的高度属性

ALV树到ISAM树的突破是,一个节点中可以存放n个key,n+1个指针,有利于在磁盘等设备上一次性存取大量数据.实际上,B 树的突破也在于此.

ISAM树
ISAM树相对B树要简单,其核心思想是把key建立成固定的索引,数据只放在leaf上,如果数据多出来,则在leaf上创建一个长链表.直接挂在树上的叫primary pages,加出来的链表叫做 Overflow pages,二者合起来就是leaf pages. 而非non-leaf pages就是 entries/index pages

B+ tree
则将ISAM和合B tree 结合, 它的数据也只放在叶节点,根和中间的节点永远是索引,但B+ tree不实用overflow pages. B+树的索引同B树一样,是在新建和删除记录时构建的
B+ tree的建立记录时,根据叶节点是否已满/索引节点是否已满,要采取不同的操作,有3种情况
1. 都不满,则直接放入在适当的位置即可
2. 叶节点已满,索引不满, 对半劈开叶节点,把叶节点中间的值做key放入索引表,索引指向新劈开的两个叶节点.然后将新建的记录放到合适的新劈开的叶节点中去
3. 都满.劈开叶节点,劈开索引节点,直到摆放合适为止.

Fill Factor在B+ tree中的作用是定义了每个节点(page)中最少的key的数量比例.如fill factor是50%, key是4,则最少的key的数量就是2.当一个节点中的key<2时,就要进行合并.