1 | /* |
2 | * Copyright 2004-2014 H2 Group. Multiple-Licensed under the MPL 2.0, |
3 | * and the EPL 1.0 (http://h2database.com/html/license.html). |
4 | * Initial Developer: H2 Group |
5 | */ |
6 | package org.h2.index; |
7 | |
8 | import org.h2.engine.Session; |
9 | import org.h2.engine.SysProperties; |
10 | import org.h2.message.DbException; |
11 | import org.h2.result.Row; |
12 | import org.h2.result.SearchRow; |
13 | import org.h2.result.SortOrder; |
14 | import org.h2.table.IndexColumn; |
15 | import org.h2.table.RegularTable; |
16 | import org.h2.table.TableFilter; |
17 | import org.h2.value.Value; |
18 | import org.h2.value.ValueNull; |
19 | |
20 | /** |
21 | * The tree index is an in-memory index based on a binary AVL trees. |
22 | */ |
23 | public class TreeIndex extends BaseIndex { |
24 | |
25 | private TreeNode root; |
26 | private final RegularTable tableData; |
27 | private long rowCount; |
28 | private boolean closed; |
29 | |
30 | public TreeIndex(RegularTable table, int id, String indexName, |
31 | IndexColumn[] columns, IndexType indexType) { |
32 | initBaseIndex(table, id, indexName, columns, indexType); |
33 | tableData = table; |
34 | if (!database.isStarting()) { |
35 | checkIndexColumnTypes(columns); |
36 | } |
37 | } |
38 | |
39 | @Override |
40 | public void close(Session session) { |
41 | root = null; |
42 | closed = true; |
43 | } |
44 | |
45 | @Override |
46 | public void add(Session session, Row row) { |
47 | if (closed) { |
48 | throw DbException.throwInternalError(); |
49 | } |
50 | TreeNode i = new TreeNode(row); |
51 | TreeNode n = root, x = n; |
52 | boolean isLeft = true; |
53 | while (true) { |
54 | if (n == null) { |
55 | if (x == null) { |
56 | root = i; |
57 | rowCount++; |
58 | return; |
59 | } |
60 | set(x, isLeft, i); |
61 | break; |
62 | } |
63 | Row r = n.row; |
64 | int compare = compareRows(row, r); |
65 | if (compare == 0) { |
66 | if (indexType.isUnique()) { |
67 | if (!containsNullAndAllowMultipleNull(row)) { |
68 | throw getDuplicateKeyException(row.toString()); |
69 | } |
70 | } |
71 | compare = compareKeys(row, r); |
72 | } |
73 | isLeft = compare < 0; |
74 | x = n; |
75 | n = child(x, isLeft); |
76 | } |
77 | balance(x, isLeft); |
78 | rowCount++; |
79 | } |
80 | |
81 | private void balance(TreeNode x, boolean isLeft) { |
82 | while (true) { |
83 | int sign = isLeft ? 1 : -1; |
84 | switch (x.balance * sign) { |
85 | case 1: |
86 | x.balance = 0; |
87 | return; |
88 | case 0: |
89 | x.balance = -sign; |
90 | break; |
91 | case -1: |
92 | TreeNode l = child(x, isLeft); |
93 | if (l.balance == -sign) { |
94 | replace(x, l); |
95 | set(x, isLeft, child(l, !isLeft)); |
96 | set(l, !isLeft, x); |
97 | x.balance = 0; |
98 | l.balance = 0; |
99 | } else { |
100 | TreeNode r = child(l, !isLeft); |
101 | replace(x, r); |
102 | set(l, !isLeft, child(r, isLeft)); |
103 | set(r, isLeft, l); |
104 | set(x, isLeft, child(r, !isLeft)); |
105 | set(r, !isLeft, x); |
106 | int rb = r.balance; |
107 | x.balance = (rb == -sign) ? sign : 0; |
108 | l.balance = (rb == sign) ? -sign : 0; |
109 | r.balance = 0; |
110 | } |
111 | return; |
112 | default: |
113 | DbException.throwInternalError("b:" + x.balance * sign); |
114 | } |
115 | if (x == root) { |
116 | return; |
117 | } |
118 | isLeft = x.isFromLeft(); |
119 | x = x.parent; |
120 | } |
121 | } |
122 | |
123 | private static TreeNode child(TreeNode x, boolean isLeft) { |
124 | return isLeft ? x.left : x.right; |
125 | } |
126 | |
127 | private void replace(TreeNode x, TreeNode n) { |
128 | if (x == root) { |
129 | root = n; |
130 | if (n != null) { |
131 | n.parent = null; |
132 | } |
133 | } else { |
134 | set(x.parent, x.isFromLeft(), n); |
135 | } |
136 | } |
137 | |
138 | private static void set(TreeNode parent, boolean left, TreeNode n) { |
139 | if (left) { |
140 | parent.left = n; |
141 | } else { |
142 | parent.right = n; |
143 | } |
144 | if (n != null) { |
145 | n.parent = parent; |
146 | } |
147 | } |
148 | |
149 | @Override |
150 | public void remove(Session session, Row row) { |
151 | if (closed) { |
152 | throw DbException.throwInternalError(); |
153 | } |
154 | TreeNode x = findFirstNode(row, true); |
155 | if (x == null) { |
156 | throw DbException.throwInternalError("not found!"); |
157 | } |
158 | TreeNode n; |
159 | if (x.left == null) { |
160 | n = x.right; |
161 | } else if (x.right == null) { |
162 | n = x.left; |
163 | } else { |
164 | TreeNode d = x; |
165 | x = x.left; |
166 | for (TreeNode temp = x; (temp = temp.right) != null;) { |
167 | x = temp; |
168 | } |
169 | // x will be replaced with n later |
170 | n = x.left; |
171 | // swap d and x |
172 | int b = x.balance; |
173 | x.balance = d.balance; |
174 | d.balance = b; |
175 | |
176 | // set x.parent |
177 | TreeNode xp = x.parent; |
178 | TreeNode dp = d.parent; |
179 | if (d == root) { |
180 | root = x; |
181 | } |
182 | x.parent = dp; |
183 | if (dp != null) { |
184 | if (dp.right == d) { |
185 | dp.right = x; |
186 | } else { |
187 | dp.left = x; |
188 | } |
189 | } |
190 | // TODO index / tree: link d.r = x(p?).r directly |
191 | if (xp == d) { |
192 | d.parent = x; |
193 | if (d.left == x) { |
194 | x.left = d; |
195 | x.right = d.right; |
196 | } else { |
197 | x.right = d; |
198 | x.left = d.left; |
199 | } |
200 | } else { |
201 | d.parent = xp; |
202 | xp.right = d; |
203 | x.right = d.right; |
204 | x.left = d.left; |
205 | } |
206 | |
207 | if (SysProperties.CHECK && x.right == null) { |
208 | DbException.throwInternalError("tree corrupted"); |
209 | } |
210 | x.right.parent = x; |
211 | x.left.parent = x; |
212 | // set d.left, d.right |
213 | d.left = n; |
214 | if (n != null) { |
215 | n.parent = d; |
216 | } |
217 | d.right = null; |
218 | x = d; |
219 | } |
220 | rowCount--; |
221 | |
222 | boolean isLeft = x.isFromLeft(); |
223 | replace(x, n); |
224 | n = x.parent; |
225 | while (n != null) { |
226 | x = n; |
227 | int sign = isLeft ? 1 : -1; |
228 | switch (x.balance * sign) { |
229 | case -1: |
230 | x.balance = 0; |
231 | break; |
232 | case 0: |
233 | x.balance = sign; |
234 | return; |
235 | case 1: |
236 | TreeNode r = child(x, !isLeft); |
237 | int b = r.balance; |
238 | if (b * sign >= 0) { |
239 | replace(x, r); |
240 | set(x, !isLeft, child(r, isLeft)); |
241 | set(r, isLeft, x); |
242 | if (b == 0) { |
243 | x.balance = sign; |
244 | r.balance = -sign; |
245 | return; |
246 | } |
247 | x.balance = 0; |
248 | r.balance = 0; |
249 | x = r; |
250 | } else { |
251 | TreeNode l = child(r, isLeft); |
252 | replace(x, l); |
253 | b = l.balance; |
254 | set(r, isLeft, child(l, !isLeft)); |
255 | set(l, !isLeft, r); |
256 | set(x, !isLeft, child(l, isLeft)); |
257 | set(l, isLeft, x); |
258 | x.balance = (b == sign) ? -sign : 0; |
259 | r.balance = (b == -sign) ? sign : 0; |
260 | l.balance = 0; |
261 | x = l; |
262 | } |
263 | break; |
264 | default: |
265 | DbException.throwInternalError("b: " + x.balance * sign); |
266 | } |
267 | isLeft = x.isFromLeft(); |
268 | n = x.parent; |
269 | } |
270 | } |
271 | |
272 | private TreeNode findFirstNode(SearchRow row, boolean withKey) { |
273 | TreeNode x = root, result = x; |
274 | while (x != null) { |
275 | result = x; |
276 | int compare = compareRows(x.row, row); |
277 | if (compare == 0 && withKey) { |
278 | compare = compareKeys(x.row, row); |
279 | } |
280 | if (compare == 0) { |
281 | if (withKey) { |
282 | return x; |
283 | } |
284 | x = x.left; |
285 | } else if (compare > 0) { |
286 | x = x.left; |
287 | } else { |
288 | x = x.right; |
289 | } |
290 | } |
291 | return result; |
292 | } |
293 | |
294 | @Override |
295 | public Cursor find(TableFilter filter, SearchRow first, SearchRow last) { |
296 | return find(first, last); |
297 | } |
298 | |
299 | @Override |
300 | public Cursor find(Session session, SearchRow first, SearchRow last) { |
301 | return find(first, last); |
302 | } |
303 | |
304 | private Cursor find(SearchRow first, SearchRow last) { |
305 | if (first == null) { |
306 | TreeNode x = root, n; |
307 | while (x != null) { |
308 | n = x.left; |
309 | if (n == null) { |
310 | break; |
311 | } |
312 | x = n; |
313 | } |
314 | return new TreeCursor(this, x, null, last); |
315 | } |
316 | TreeNode x = findFirstNode(first, false); |
317 | return new TreeCursor(this, x, first, last); |
318 | } |
319 | |
320 | @Override |
321 | public double getCost(Session session, int[] masks, TableFilter filter, |
322 | SortOrder sortOrder) { |
323 | return getCostRangeIndex(masks, tableData.getRowCountApproximation(), |
324 | filter, sortOrder); |
325 | } |
326 | |
327 | @Override |
328 | public void remove(Session session) { |
329 | truncate(session); |
330 | } |
331 | |
332 | @Override |
333 | public void truncate(Session session) { |
334 | root = null; |
335 | rowCount = 0; |
336 | } |
337 | |
338 | @Override |
339 | public void checkRename() { |
340 | // nothing to do |
341 | } |
342 | |
343 | @Override |
344 | public boolean needRebuild() { |
345 | return true; |
346 | } |
347 | |
348 | @Override |
349 | public boolean canGetFirstOrLast() { |
350 | return true; |
351 | } |
352 | |
353 | @Override |
354 | public Cursor findFirstOrLast(Session session, boolean first) { |
355 | if (closed) { |
356 | throw DbException.throwInternalError(); |
357 | } |
358 | if (first) { |
359 | // TODO optimization: this loops through NULL |
360 | Cursor cursor = find(session, null, null); |
361 | while (cursor.next()) { |
362 | SearchRow row = cursor.getSearchRow(); |
363 | Value v = row.getValue(columnIds[0]); |
364 | if (v != ValueNull.INSTANCE) { |
365 | return cursor; |
366 | } |
367 | } |
368 | return cursor; |
369 | } |
370 | TreeNode x = root, n; |
371 | while (x != null) { |
372 | n = x.right; |
373 | if (n == null) { |
374 | break; |
375 | } |
376 | x = n; |
377 | } |
378 | TreeCursor cursor = new TreeCursor(this, x, null, null); |
379 | if (x == null) { |
380 | return cursor; |
381 | } |
382 | // TODO optimization: this loops through NULL elements |
383 | do { |
384 | SearchRow row = cursor.getSearchRow(); |
385 | if (row == null) { |
386 | break; |
387 | } |
388 | Value v = row.getValue(columnIds[0]); |
389 | if (v != ValueNull.INSTANCE) { |
390 | return cursor; |
391 | } |
392 | } while (cursor.previous()); |
393 | return cursor; |
394 | } |
395 | |
396 | @Override |
397 | public long getRowCount(Session session) { |
398 | return rowCount; |
399 | } |
400 | |
401 | @Override |
402 | public long getRowCountApproximation() { |
403 | return rowCount; |
404 | } |
405 | |
406 | @Override |
407 | public long getDiskSpaceUsed() { |
408 | return 0; |
409 | } |
410 | |
411 | } |