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 | |
10 | import org.h2.api.ErrorCode; |
11 | import org.h2.engine.Constants; |
12 | import org.h2.engine.Session; |
13 | import org.h2.engine.SysProperties; |
14 | import org.h2.message.DbException; |
15 | import org.h2.result.SearchRow; |
16 | import org.h2.store.Data; |
17 | import org.h2.store.Page; |
18 | import org.h2.store.PageStore; |
19 | |
20 | /** |
21 | * A b-tree leaf page that contains index data. Format: |
22 | * <ul> |
23 | * <li>page type: byte</li> |
24 | * <li>checksum: short</li> |
25 | * <li>parent page id (0 for root): int</li> |
26 | * <li>index id: varInt</li> |
27 | * <li>entry count: short</li> |
28 | * <li>list of offsets: short</li> |
29 | * <li>data (key: varLong, value,...)</li> |
30 | * </ul> |
31 | */ |
32 | public class PageBtreeLeaf extends PageBtree { |
33 | |
34 | private static final int OFFSET_LENGTH = 2; |
35 | |
36 | private final boolean optimizeUpdate; |
37 | private boolean writtenData; |
38 | |
39 | private PageBtreeLeaf(PageBtreeIndex index, int pageId, Data data) { |
40 | super(index, pageId, data); |
41 | this.optimizeUpdate = index.getDatabase().getSettings().optimizeUpdate; |
42 | } |
43 | |
44 | /** |
45 | * Read a b-tree leaf page. |
46 | * |
47 | * @param index the index |
48 | * @param data the data |
49 | * @param pageId the page id |
50 | * @return the page |
51 | */ |
52 | public static Page read(PageBtreeIndex index, Data data, int pageId) { |
53 | PageBtreeLeaf p = new PageBtreeLeaf(index, pageId, data); |
54 | p.read(); |
55 | return p; |
56 | } |
57 | |
58 | /** |
59 | * Create a new page. |
60 | * |
61 | * @param index the index |
62 | * @param pageId the page id |
63 | * @param parentPageId the parent |
64 | * @return the page |
65 | */ |
66 | static PageBtreeLeaf create(PageBtreeIndex index, int pageId, |
67 | int parentPageId) { |
68 | PageBtreeLeaf p = new PageBtreeLeaf(index, pageId, index.getPageStore() |
69 | .createData()); |
70 | index.getPageStore().logUndo(p, null); |
71 | p.rows = SearchRow.EMPTY_ARRAY; |
72 | p.parentPageId = parentPageId; |
73 | p.writeHead(); |
74 | p.start = p.data.length(); |
75 | return p; |
76 | } |
77 | |
78 | private void read() { |
79 | data.reset(); |
80 | int type = data.readByte(); |
81 | data.readShortInt(); |
82 | this.parentPageId = data.readInt(); |
83 | onlyPosition = (type & Page.FLAG_LAST) == 0; |
84 | int indexId = data.readVarInt(); |
85 | if (indexId != index.getId()) { |
86 | throw DbException.get(ErrorCode.FILE_CORRUPTED_1, |
87 | "page:" + getPos() + " expected index:" + index.getId() + |
88 | "got:" + indexId); |
89 | } |
90 | entryCount = data.readShortInt(); |
91 | offsets = new int[entryCount]; |
92 | rows = new SearchRow[entryCount]; |
93 | for (int i = 0; i < entryCount; i++) { |
94 | offsets[i] = data.readShortInt(); |
95 | } |
96 | start = data.length(); |
97 | written = true; |
98 | writtenData = true; |
99 | } |
100 | |
101 | @Override |
102 | int addRowTry(SearchRow row) { |
103 | int x = addRow(row, true); |
104 | memoryChange(); |
105 | return x; |
106 | } |
107 | |
108 | private int addRow(SearchRow row, boolean tryOnly) { |
109 | int rowLength = index.getRowSize(data, row, onlyPosition); |
110 | int pageSize = index.getPageStore().getPageSize(); |
111 | int last = entryCount == 0 ? pageSize : offsets[entryCount - 1]; |
112 | if (last - rowLength < start + OFFSET_LENGTH) { |
113 | if (tryOnly && entryCount > 1) { |
114 | int x = find(row, false, true, true); |
115 | if (entryCount < 5) { |
116 | // required, otherwise the index doesn't work correctly |
117 | return entryCount / 2; |
118 | } |
119 | // split near the insertion point to better fill pages |
120 | // split in half would be: |
121 | // return entryCount / 2; |
122 | int third = entryCount / 3; |
123 | return x < third ? third : x >= 2 * third ? 2 * third : x; |
124 | } |
125 | readAllRows(); |
126 | writtenData = false; |
127 | onlyPosition = true; |
128 | // change the offsets (now storing only positions) |
129 | int o = pageSize; |
130 | for (int i = 0; i < entryCount; i++) { |
131 | o -= index.getRowSize(data, getRow(i), true); |
132 | offsets[i] = o; |
133 | } |
134 | last = entryCount == 0 ? pageSize : offsets[entryCount - 1]; |
135 | rowLength = index.getRowSize(data, row, true); |
136 | if (SysProperties.CHECK && last - rowLength < start + OFFSET_LENGTH) { |
137 | throw DbException.throwInternalError(); |
138 | } |
139 | } |
140 | index.getPageStore().logUndo(this, data); |
141 | if (!optimizeUpdate) { |
142 | readAllRows(); |
143 | } |
144 | changeCount = index.getPageStore().getChangeCount(); |
145 | written = false; |
146 | int x; |
147 | if (entryCount == 0) { |
148 | x = 0; |
149 | } else { |
150 | x = find(row, false, true, true); |
151 | } |
152 | start += OFFSET_LENGTH; |
153 | int offset = (x == 0 ? pageSize : offsets[x - 1]) - rowLength; |
154 | if (optimizeUpdate && writtenData) { |
155 | if (entryCount > 0) { |
156 | byte[] d = data.getBytes(); |
157 | int dataStart = offsets[entryCount - 1]; |
158 | int dataEnd = offset; |
159 | System.arraycopy(d, dataStart, d, dataStart - rowLength, |
160 | dataEnd - dataStart + rowLength); |
161 | } |
162 | index.writeRow(data, offset, row, onlyPosition); |
163 | } |
164 | offsets = insert(offsets, entryCount, x, offset); |
165 | add(offsets, x + 1, entryCount + 1, -rowLength); |
166 | rows = insert(rows, entryCount, x, row); |
167 | entryCount++; |
168 | index.getPageStore().update(this); |
169 | return -1; |
170 | } |
171 | |
172 | private void removeRow(int at) { |
173 | if (!optimizeUpdate) { |
174 | readAllRows(); |
175 | } |
176 | index.getPageStore().logUndo(this, data); |
177 | entryCount--; |
178 | written = false; |
179 | changeCount = index.getPageStore().getChangeCount(); |
180 | if (entryCount <= 0) { |
181 | DbException.throwInternalError(); |
182 | } |
183 | int startNext = at > 0 ? offsets[at - 1] : index.getPageStore().getPageSize(); |
184 | int rowLength = startNext - offsets[at]; |
185 | start -= OFFSET_LENGTH; |
186 | |
187 | if (optimizeUpdate) { |
188 | if (writtenData) { |
189 | byte[] d = data.getBytes(); |
190 | int dataStart = offsets[entryCount]; |
191 | System.arraycopy(d, dataStart, d, |
192 | dataStart + rowLength, offsets[at] - dataStart); |
193 | Arrays.fill(d, dataStart, dataStart + rowLength, (byte) 0); |
194 | } |
195 | } |
196 | |
197 | offsets = remove(offsets, entryCount + 1, at); |
198 | add(offsets, at, entryCount, rowLength); |
199 | rows = remove(rows, entryCount + 1, at); |
200 | } |
201 | |
202 | int getEntryCount() { |
203 | return entryCount; |
204 | } |
205 | |
206 | @Override |
207 | PageBtree split(int splitPoint) { |
208 | int newPageId = index.getPageStore().allocatePage(); |
209 | PageBtreeLeaf p2 = PageBtreeLeaf.create(index, newPageId, parentPageId); |
210 | for (int i = splitPoint; i < entryCount;) { |
211 | p2.addRow(getRow(splitPoint), false); |
212 | removeRow(splitPoint); |
213 | } |
214 | memoryChange(); |
215 | p2.memoryChange(); |
216 | return p2; |
217 | } |
218 | |
219 | @Override |
220 | PageBtreeLeaf getFirstLeaf() { |
221 | return this; |
222 | } |
223 | |
224 | @Override |
225 | PageBtreeLeaf getLastLeaf() { |
226 | return this; |
227 | } |
228 | |
229 | @Override |
230 | SearchRow remove(SearchRow row) { |
231 | int at = find(row, false, false, true); |
232 | SearchRow delete = getRow(at); |
233 | if (index.compareRows(row, delete) != 0 || delete.getKey() != row.getKey()) { |
234 | throw DbException.get(ErrorCode.ROW_NOT_FOUND_WHEN_DELETING_1, |
235 | index.getSQL() + ": " + row); |
236 | } |
237 | index.getPageStore().logUndo(this, data); |
238 | if (entryCount == 1) { |
239 | // the page is now empty |
240 | return row; |
241 | } |
242 | removeRow(at); |
243 | memoryChange(); |
244 | index.getPageStore().update(this); |
245 | if (at == entryCount) { |
246 | // the last row changed |
247 | return getRow(at - 1); |
248 | } |
249 | // the last row didn't change |
250 | return null; |
251 | } |
252 | |
253 | @Override |
254 | void freeRecursive() { |
255 | index.getPageStore().logUndo(this, data); |
256 | index.getPageStore().free(getPos()); |
257 | } |
258 | |
259 | @Override |
260 | int getRowCount() { |
261 | return entryCount; |
262 | } |
263 | |
264 | @Override |
265 | void setRowCountStored(int rowCount) { |
266 | // ignore |
267 | } |
268 | |
269 | @Override |
270 | public void write() { |
271 | writeData(); |
272 | index.getPageStore().writePage(getPos(), data); |
273 | } |
274 | |
275 | private void writeHead() { |
276 | data.reset(); |
277 | data.writeByte((byte) (Page.TYPE_BTREE_LEAF | |
278 | (onlyPosition ? 0 : Page.FLAG_LAST))); |
279 | data.writeShortInt(0); |
280 | data.writeInt(parentPageId); |
281 | data.writeVarInt(index.getId()); |
282 | data.writeShortInt(entryCount); |
283 | } |
284 | |
285 | private void writeData() { |
286 | if (written) { |
287 | return; |
288 | } |
289 | if (!optimizeUpdate) { |
290 | readAllRows(); |
291 | } |
292 | writeHead(); |
293 | for (int i = 0; i < entryCount; i++) { |
294 | data.writeShortInt(offsets[i]); |
295 | } |
296 | if (!writtenData || !optimizeUpdate) { |
297 | for (int i = 0; i < entryCount; i++) { |
298 | index.writeRow(data, offsets[i], rows[i], onlyPosition); |
299 | } |
300 | writtenData = true; |
301 | } |
302 | written = true; |
303 | memoryChange(); |
304 | } |
305 | |
306 | @Override |
307 | void find(PageBtreeCursor cursor, SearchRow first, boolean bigger) { |
308 | int i = find(first, bigger, false, false); |
309 | if (i > entryCount) { |
310 | if (parentPageId == PageBtree.ROOT) { |
311 | return; |
312 | } |
313 | PageBtreeNode next = (PageBtreeNode) index.getPage(parentPageId); |
314 | next.find(cursor, first, bigger); |
315 | return; |
316 | } |
317 | cursor.setCurrent(this, i); |
318 | } |
319 | |
320 | @Override |
321 | void last(PageBtreeCursor cursor) { |
322 | cursor.setCurrent(this, entryCount - 1); |
323 | } |
324 | |
325 | @Override |
326 | void remapChildren() { |
327 | // nothing to do |
328 | } |
329 | |
330 | /** |
331 | * Set the cursor to the first row of the next page. |
332 | * |
333 | * @param cursor the cursor |
334 | */ |
335 | void nextPage(PageBtreeCursor cursor) { |
336 | if (parentPageId == PageBtree.ROOT) { |
337 | cursor.setCurrent(null, 0); |
338 | return; |
339 | } |
340 | PageBtreeNode next = (PageBtreeNode) index.getPage(parentPageId); |
341 | next.nextPage(cursor, getPos()); |
342 | } |
343 | |
344 | /** |
345 | * Set the cursor to the last row of the previous page. |
346 | * |
347 | * @param cursor the cursor |
348 | */ |
349 | void previousPage(PageBtreeCursor cursor) { |
350 | if (parentPageId == PageBtree.ROOT) { |
351 | cursor.setCurrent(null, 0); |
352 | return; |
353 | } |
354 | PageBtreeNode next = (PageBtreeNode) index.getPage(parentPageId); |
355 | next.previousPage(cursor, getPos()); |
356 | } |
357 | |
358 | @Override |
359 | public String toString() { |
360 | return "page[" + getPos() + "] b-tree leaf table:" + |
361 | index.getId() + " entries:" + entryCount; |
362 | } |
363 | |
364 | @Override |
365 | public void moveTo(Session session, int newPos) { |
366 | PageStore store = index.getPageStore(); |
367 | readAllRows(); |
368 | PageBtreeLeaf p2 = PageBtreeLeaf.create(index, newPos, parentPageId); |
369 | store.logUndo(this, data); |
370 | store.logUndo(p2, null); |
371 | p2.rows = rows; |
372 | p2.entryCount = entryCount; |
373 | p2.offsets = offsets; |
374 | p2.onlyPosition = onlyPosition; |
375 | p2.parentPageId = parentPageId; |
376 | p2.start = start; |
377 | store.update(p2); |
378 | if (parentPageId == ROOT) { |
379 | index.setRootPageId(session, newPos); |
380 | } else { |
381 | PageBtreeNode p = (PageBtreeNode) store.getPage(parentPageId); |
382 | p.moveChild(getPos(), newPos); |
383 | } |
384 | store.free(getPos()); |
385 | } |
386 | |
387 | @Override |
388 | protected void memoryChange() { |
389 | if (!PageBtreeIndex.isMemoryChangeRequired()) { |
390 | return; |
391 | } |
392 | int memory = Constants.MEMORY_PAGE_BTREE + index.getPageStore().getPageSize(); |
393 | if (rows != null) { |
394 | memory += getEntryCount() * (4 + Constants.MEMORY_POINTER); |
395 | for (int i = 0; i < entryCount; i++) { |
396 | SearchRow r = rows[i]; |
397 | if (r != null) { |
398 | memory += r.getMemory(); |
399 | } |
400 | } |
401 | } |
402 | index.memoryChange(memory >> 2); |
403 | } |
404 | |
405 | } |