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 java.util.Arrays; |
9 | import org.h2.api.DatabaseEventListener; |
10 | import org.h2.api.ErrorCode; |
11 | import org.h2.engine.Session; |
12 | import org.h2.engine.SysProperties; |
13 | import org.h2.message.DbException; |
14 | import org.h2.result.Row; |
15 | import org.h2.store.Data; |
16 | import org.h2.store.Page; |
17 | import org.h2.store.PageStore; |
18 | import org.h2.util.Utils; |
19 | |
20 | /** |
21 | * A leaf page that contains data of one or multiple rows. Format: |
22 | * <ul> |
23 | * <li>page type: byte (0)</li> |
24 | * <li>checksum: short (1-2)</li> |
25 | * <li>parent page id (0 for root): int (3-6)</li> |
26 | * <li>table id: varInt</li> |
27 | * <li>count of all children (-1 if not known): int</li> |
28 | * <li>entry count: short</li> |
29 | * <li>rightmost child page id: int</li> |
30 | * <li>entries (child page id: int, key: varLong)</li> |
31 | * </ul> |
32 | * The key is the largest key of the respective child, meaning key[0] is the |
33 | * largest key of child[0]. |
34 | */ |
35 | public class PageDataNode extends PageData { |
36 | |
37 | /** |
38 | * The page ids of the children. |
39 | */ |
40 | private int[] childPageIds; |
41 | |
42 | private int rowCountStored = UNKNOWN_ROWCOUNT; |
43 | |
44 | private int rowCount = UNKNOWN_ROWCOUNT; |
45 | |
46 | /** |
47 | * The number of bytes used in the page |
48 | */ |
49 | private int length; |
50 | |
51 | private PageDataNode(PageDataIndex index, int pageId, Data data) { |
52 | super(index, pageId, data); |
53 | } |
54 | |
55 | /** |
56 | * Create a new page. |
57 | * |
58 | * @param index the index |
59 | * @param pageId the page id |
60 | * @param parentPageId the parent |
61 | * @return the page |
62 | */ |
63 | static PageDataNode create(PageDataIndex index, int pageId, int parentPageId) { |
64 | PageDataNode p = new PageDataNode(index, pageId, |
65 | index.getPageStore().createData()); |
66 | index.getPageStore().logUndo(p, null); |
67 | p.parentPageId = parentPageId; |
68 | p.writeHead(); |
69 | // 4 bytes for the rightmost child page id |
70 | p.length = p.data.length() + 4; |
71 | return p; |
72 | } |
73 | |
74 | /** |
75 | * Read a data node page. |
76 | * |
77 | * @param index the index |
78 | * @param data the data |
79 | * @param pageId the page id |
80 | * @return the page |
81 | */ |
82 | public static Page read(PageDataIndex index, Data data, int pageId) { |
83 | PageDataNode p = new PageDataNode(index, pageId, data); |
84 | p.read(); |
85 | return p; |
86 | } |
87 | |
88 | private void read() { |
89 | data.reset(); |
90 | data.readByte(); |
91 | data.readShortInt(); |
92 | this.parentPageId = data.readInt(); |
93 | int indexId = data.readVarInt(); |
94 | if (indexId != index.getId()) { |
95 | throw DbException.get(ErrorCode.FILE_CORRUPTED_1, |
96 | "page:" + getPos() + " expected index:" + index.getId() + |
97 | "got:" + indexId); |
98 | } |
99 | rowCount = rowCountStored = data.readInt(); |
100 | entryCount = data.readShortInt(); |
101 | childPageIds = new int[entryCount + 1]; |
102 | childPageIds[entryCount] = data.readInt(); |
103 | keys = Utils.newLongArray(entryCount); |
104 | for (int i = 0; i < entryCount; i++) { |
105 | childPageIds[i] = data.readInt(); |
106 | keys[i] = data.readVarLong(); |
107 | } |
108 | length = data.length(); |
109 | check(); |
110 | written = true; |
111 | } |
112 | |
113 | private void addChild(int x, int childPageId, long key) { |
114 | index.getPageStore().logUndo(this, data); |
115 | written = false; |
116 | changeCount = index.getPageStore().getChangeCount(); |
117 | childPageIds = insert(childPageIds, entryCount + 1, x + 1, childPageId); |
118 | keys = insert(keys, entryCount, x, key); |
119 | entryCount++; |
120 | length += 4 + Data.getVarLongLen(key); |
121 | } |
122 | |
123 | @Override |
124 | int addRowTry(Row row) { |
125 | index.getPageStore().logUndo(this, data); |
126 | int keyOffsetPairLen = 4 + Data.getVarLongLen(row.getKey()); |
127 | while (true) { |
128 | int x = find(row.getKey()); |
129 | PageData page = index.getPage(childPageIds[x], getPos()); |
130 | int splitPoint = page.addRowTry(row); |
131 | if (splitPoint == -1) { |
132 | break; |
133 | } |
134 | if (length + keyOffsetPairLen > index.getPageStore().getPageSize()) { |
135 | return entryCount / 2; |
136 | } |
137 | long pivot = splitPoint == 0 ? row.getKey() : page.getKey(splitPoint - 1); |
138 | PageData page2 = page.split(splitPoint); |
139 | index.getPageStore().update(page); |
140 | index.getPageStore().update(page2); |
141 | addChild(x, page2.getPos(), pivot); |
142 | index.getPageStore().update(this); |
143 | } |
144 | updateRowCount(1); |
145 | return -1; |
146 | } |
147 | |
148 | private void updateRowCount(int offset) { |
149 | if (rowCount != UNKNOWN_ROWCOUNT) { |
150 | rowCount += offset; |
151 | } |
152 | if (rowCountStored != UNKNOWN_ROWCOUNT) { |
153 | rowCountStored = UNKNOWN_ROWCOUNT; |
154 | index.getPageStore().logUndo(this, data); |
155 | if (written) { |
156 | writeHead(); |
157 | } |
158 | index.getPageStore().update(this); |
159 | } |
160 | } |
161 | |
162 | @Override |
163 | Cursor find(Session session, long minKey, long maxKey, boolean multiVersion) { |
164 | int x = find(minKey); |
165 | int child = childPageIds[x]; |
166 | return index.getPage(child, getPos()).find(session, minKey, maxKey, |
167 | multiVersion); |
168 | } |
169 | |
170 | @Override |
171 | PageData split(int splitPoint) { |
172 | int newPageId = index.getPageStore().allocatePage(); |
173 | PageDataNode p2 = PageDataNode.create(index, newPageId, parentPageId); |
174 | int firstChild = childPageIds[splitPoint]; |
175 | for (int i = splitPoint; i < entryCount;) { |
176 | p2.addChild(p2.entryCount, childPageIds[splitPoint + 1], keys[splitPoint]); |
177 | removeChild(splitPoint); |
178 | } |
179 | int lastChild = childPageIds[splitPoint - 1]; |
180 | removeChild(splitPoint - 1); |
181 | childPageIds[splitPoint - 1] = lastChild; |
182 | p2.childPageIds[0] = firstChild; |
183 | p2.remapChildren(getPos()); |
184 | return p2; |
185 | } |
186 | |
187 | @Override |
188 | protected void remapChildren(int old) { |
189 | for (int i = 0; i < entryCount + 1; i++) { |
190 | int child = childPageIds[i]; |
191 | PageData p = index.getPage(child, old); |
192 | p.setParentPageId(getPos()); |
193 | index.getPageStore().update(p); |
194 | } |
195 | } |
196 | |
197 | /** |
198 | * Initialize the page. |
199 | * |
200 | * @param page1 the first child page |
201 | * @param pivot the pivot key |
202 | * @param page2 the last child page |
203 | */ |
204 | void init(PageData page1, long pivot, PageData page2) { |
205 | entryCount = 1; |
206 | childPageIds = new int[] { page1.getPos(), page2.getPos() }; |
207 | keys = new long[] { pivot }; |
208 | length += 4 + Data.getVarLongLen(pivot); |
209 | check(); |
210 | } |
211 | |
212 | @Override |
213 | long getLastKey() { |
214 | return index.getPage(childPageIds[entryCount], getPos()).getLastKey(); |
215 | } |
216 | |
217 | /** |
218 | * Get the next leaf page. |
219 | * |
220 | * @param key the last key of the current page |
221 | * @return the next leaf page |
222 | */ |
223 | PageDataLeaf getNextPage(long key) { |
224 | int i = find(key) + 1; |
225 | if (i > entryCount) { |
226 | if (parentPageId == PageData.ROOT) { |
227 | return null; |
228 | } |
229 | PageDataNode next = (PageDataNode) index.getPage(parentPageId, -1); |
230 | return next.getNextPage(key); |
231 | } |
232 | PageData page = index.getPage(childPageIds[i], getPos()); |
233 | return page.getFirstLeaf(); |
234 | } |
235 | |
236 | @Override |
237 | PageDataLeaf getFirstLeaf() { |
238 | int child = childPageIds[0]; |
239 | return index.getPage(child, getPos()).getFirstLeaf(); |
240 | } |
241 | |
242 | @Override |
243 | boolean remove(long key) { |
244 | int at = find(key); |
245 | // merge is not implemented to allow concurrent usage |
246 | // TODO maybe implement merge |
247 | PageData page = index.getPage(childPageIds[at], getPos()); |
248 | boolean empty = page.remove(key); |
249 | index.getPageStore().logUndo(this, data); |
250 | updateRowCount(-1); |
251 | if (!empty) { |
252 | // the first row didn't change - nothing to do |
253 | return false; |
254 | } |
255 | // this child is now empty |
256 | index.getPageStore().free(page.getPos()); |
257 | if (entryCount < 1) { |
258 | // no more children - this page is empty as well |
259 | return true; |
260 | } |
261 | removeChild(at); |
262 | index.getPageStore().update(this); |
263 | return false; |
264 | } |
265 | |
266 | @Override |
267 | void freeRecursive() { |
268 | index.getPageStore().logUndo(this, data); |
269 | index.getPageStore().free(getPos()); |
270 | for (int i = 0; i < entryCount + 1; i++) { |
271 | int child = childPageIds[i]; |
272 | index.getPage(child, getPos()).freeRecursive(); |
273 | } |
274 | } |
275 | |
276 | @Override |
277 | Row getRowWithKey(long key) { |
278 | int at = find(key); |
279 | PageData page = index.getPage(childPageIds[at], getPos()); |
280 | return page.getRowWithKey(key); |
281 | } |
282 | |
283 | @Override |
284 | int getRowCount() { |
285 | if (rowCount == UNKNOWN_ROWCOUNT) { |
286 | int count = 0; |
287 | for (int i = 0; i < entryCount + 1; i++) { |
288 | int child = childPageIds[i]; |
289 | PageData page = index.getPage(child, getPos()); |
290 | if (getPos() == page.getPos()) { |
291 | throw DbException.throwInternalError("Page is its own child: " + getPos()); |
292 | } |
293 | count += page.getRowCount(); |
294 | index.getDatabase().setProgress(DatabaseEventListener.STATE_SCAN_FILE, |
295 | index.getTable() + "." + index.getName(), count, Integer.MAX_VALUE); |
296 | } |
297 | rowCount = count; |
298 | } |
299 | return rowCount; |
300 | } |
301 | |
302 | @Override |
303 | long getDiskSpaceUsed() { |
304 | long count = 0; |
305 | for (int i = 0; i < entryCount + 1; i++) { |
306 | int child = childPageIds[i]; |
307 | PageData page = index.getPage(child, getPos()); |
308 | if (getPos() == page.getPos()) { |
309 | throw DbException.throwInternalError("Page is its own child: " + getPos()); |
310 | } |
311 | count += page.getDiskSpaceUsed(); |
312 | index.getDatabase().setProgress(DatabaseEventListener.STATE_SCAN_FILE, |
313 | index.getTable() + "." + index.getName(), |
314 | (int) (count >> 16), Integer.MAX_VALUE); |
315 | } |
316 | return count; |
317 | } |
318 | |
319 | @Override |
320 | void setRowCountStored(int rowCount) { |
321 | this.rowCount = rowCount; |
322 | if (rowCountStored != rowCount) { |
323 | rowCountStored = rowCount; |
324 | index.getPageStore().logUndo(this, data); |
325 | if (written) { |
326 | changeCount = index.getPageStore().getChangeCount(); |
327 | writeHead(); |
328 | } |
329 | index.getPageStore().update(this); |
330 | } |
331 | } |
332 | |
333 | private void check() { |
334 | if (SysProperties.CHECK) { |
335 | for (int i = 0; i < entryCount + 1; i++) { |
336 | int child = childPageIds[i]; |
337 | if (child == 0) { |
338 | DbException.throwInternalError(); |
339 | } |
340 | } |
341 | } |
342 | } |
343 | |
344 | @Override |
345 | public void write() { |
346 | writeData(); |
347 | index.getPageStore().writePage(getPos(), data); |
348 | } |
349 | |
350 | private void writeHead() { |
351 | data.reset(); |
352 | data.writeByte((byte) Page.TYPE_DATA_NODE); |
353 | data.writeShortInt(0); |
354 | if (SysProperties.CHECK2) { |
355 | if (data.length() != START_PARENT) { |
356 | DbException.throwInternalError(); |
357 | } |
358 | } |
359 | data.writeInt(parentPageId); |
360 | data.writeVarInt(index.getId()); |
361 | data.writeInt(rowCountStored); |
362 | data.writeShortInt(entryCount); |
363 | } |
364 | |
365 | private void writeData() { |
366 | if (written) { |
367 | return; |
368 | } |
369 | check(); |
370 | writeHead(); |
371 | data.writeInt(childPageIds[entryCount]); |
372 | for (int i = 0; i < entryCount; i++) { |
373 | data.writeInt(childPageIds[i]); |
374 | data.writeVarLong(keys[i]); |
375 | } |
376 | if (length != data.length()) { |
377 | DbException.throwInternalError("expected pos: " + length + |
378 | " got: " + data.length()); |
379 | } |
380 | written = true; |
381 | } |
382 | |
383 | private void removeChild(int i) { |
384 | index.getPageStore().logUndo(this, data); |
385 | written = false; |
386 | changeCount = index.getPageStore().getChangeCount(); |
387 | int removedKeyIndex = i < entryCount ? i : i - 1; |
388 | entryCount--; |
389 | length -= 4 + Data.getVarLongLen(keys[removedKeyIndex]); |
390 | if (entryCount < 0) { |
391 | DbException.throwInternalError(); |
392 | } |
393 | keys = remove(keys, entryCount + 1, removedKeyIndex); |
394 | childPageIds = remove(childPageIds, entryCount + 2, i); |
395 | } |
396 | |
397 | @Override |
398 | public String toString() { |
399 | return "page[" + getPos() + "] data node table:" + index.getId() + |
400 | " entries:" + entryCount + " " + Arrays.toString(childPageIds); |
401 | } |
402 | |
403 | @Override |
404 | public void moveTo(Session session, int newPos) { |
405 | PageStore store = index.getPageStore(); |
406 | // load the pages into the cache, to ensure old pages |
407 | // are written |
408 | for (int i = 0; i < entryCount + 1; i++) { |
409 | int child = childPageIds[i]; |
410 | store.getPage(child); |
411 | } |
412 | if (parentPageId != ROOT) { |
413 | store.getPage(parentPageId); |
414 | } |
415 | store.logUndo(this, data); |
416 | PageDataNode p2 = PageDataNode.create(index, newPos, parentPageId); |
417 | p2.rowCountStored = rowCountStored; |
418 | p2.rowCount = rowCount; |
419 | p2.childPageIds = childPageIds; |
420 | p2.keys = keys; |
421 | p2.entryCount = entryCount; |
422 | p2.length = length; |
423 | store.update(p2); |
424 | if (parentPageId == ROOT) { |
425 | index.setRootPageId(session, newPos); |
426 | } else { |
427 | PageDataNode p = (PageDataNode) store.getPage(parentPageId); |
428 | p.moveChild(getPos(), newPos); |
429 | } |
430 | for (int i = 0; i < entryCount + 1; i++) { |
431 | int child = childPageIds[i]; |
432 | PageData p = (PageData) store.getPage(child); |
433 | p.setParentPageId(newPos); |
434 | store.update(p); |
435 | } |
436 | store.free(getPos()); |
437 | } |
438 | |
439 | /** |
440 | * One of the children has moved to another page. |
441 | * |
442 | * @param oldPos the old position |
443 | * @param newPos the new position |
444 | */ |
445 | void moveChild(int oldPos, int newPos) { |
446 | for (int i = 0; i < entryCount + 1; i++) { |
447 | if (childPageIds[i] == oldPos) { |
448 | index.getPageStore().logUndo(this, data); |
449 | written = false; |
450 | changeCount = index.getPageStore().getChangeCount(); |
451 | childPageIds[i] = newPos; |
452 | index.getPageStore().update(this); |
453 | return; |
454 | } |
455 | } |
456 | throw DbException.throwInternalError(); |
457 | } |
458 | |
459 | } |