-
Notifications
You must be signed in to change notification settings - Fork 12
/
README
104 lines (82 loc) · 2.35 KB
/
README
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
OMT is short for Order Maintenance Tree, which is dreamed up by Tokutek, and used in TokuDB.
It's a weight balanced binary tree, each node maintains the weights of its left and right subtrees.
OMT having better CPU cache efficiency than skiplist (it's very cool as you improve it to vEB layout).
For more details, please see Cartesian Tree: http://en.wikipedia.org/wiki/Cartesian_tree
Insertion as follows:
1) insert 'key-1'
/*
* (key-1)
*/
2) insert 'key-4'
/*
* (key-1)
* \
* (key-4)
*/
3) insert 'key-7'
/*
* (key-1)
* \
* (key-4)
* \
* (key-7)
*/
4) insert 'key-5'
/*
* (key-1)
* \
* (key-4)
* \
* (key-7)
* /
* (key-5)
*/
5) insert 'key-6', the tree need to be rebalanced:
/*
* (key-1)
* \
* (key-4)
* \
* (key-7)
* /
* (key-5)
* \
* (key-6)
*/
After rebalance:
/*
*
* (key-5)
* / \
* (key-4) (key-7)
* / / \
* (key-1) (key-6) (key-71)
*
*/
6) and we insert 'key-72', 'key-75', it cause a balance:
/*
*
* (key-5)
* / \
* (key-4) (key-7)
* / / \
* (key-1) (key-6) (key-71)
* \
* (key-72)
* \
* (key-75)
*
*/
/***************** after rebalance *********************/
/*
*
* (key-7)
* / \
* (key-5) (key-72)
* / \ / \
* (key-4) (key-6) (key-71) (key-75)
* /
*(key-1)
*
*/
By BohuTANG @2013/9/19