T-Tree Theory
2009-09-17 14:34:28| 分类:
dbms
| 标签:
|举报
|字号大中小 订阅
Structure for one node
- Pointer to parent/lchild/rchild
- Data pointer
- Control data
Node type
- 2 childs, internal node
- 0 child, leaf node
- 1 child, half-leaf node
- Bounding node, (match the search condition e.g. search 10, the node contain 1 to 20)
Search
Balance & rotation
- Like AVL tree
Insert
- Search a bounding node if exists
- Enough space left, insert into
- No space, remove the minimum value and insert the new value
- Find greater lower value node for it and try to insert the minimum value
- If no space left, create a right sub node for the node
- Else
- Try to insert the value into the latest node
- If needed, to create a left or right child
Deletion
- Search for bounding node of the value to be deleted. If no bounding node is found then finish, if the bounding node doesn’t contain that value, finish
- Delete the value from the array
- Internal node
- Node has minimum number elements, move the data to greatest lower
- Proceed one of following steps
- leaf node
- If this is the only one, drop this node and rebalance
- Half-leaf node
- If the data can be merged, merge it then remove leaf node, rebalance
评论这张
转发至微博
转发至微博
评论