一些树的结构备忘

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时,就要进行合并.