File D:\maven-qcr-plugin-testsunitaires\qcr4java\h2-1.3.170-sources\target\site\qc\lecode\index\PageBtreeIndex.java.html

1 /*
2 * Copyright 2004-2011 H2 Group. Multiple-Licensed under the H2 License,
3 * Version 1.0, and under the Eclipse Public License, Version 1.0
4 * (http://h2database.com/html/license.html).
5 * Initial Developer: H2 Group
6 */
7 package org.h2.index;
8
9 import org.h2.constant.ErrorCode;
10 import org.h2.constant.SysProperties;
11 import org.h2.engine.Constants;
12 import org.h2.engine.Session;
13 import org.h2.message.DbException;
14 import org.h2.result.Row;
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 import org.h2.table.Column;
20 import org.h2.table.IndexColumn;
21 import org.h2.table.RegularTable;
22 import org.h2.util.MathUtils;
23 import org.h2.value.Value;
24 import org.h2.value.ValueNull;
25
26 /**
27 * This is the most common type of index, a b tree index.
28 * Only the data of the indexed columns are stored in the index.
29 */
30 public class PageBtreeIndex extends PageIndex {
31
32 private static int memoryChangeRequired;
33
34 private final PageStore store;
35 private final RegularTable tableData;
36 private final boolean needRebuild;
37 private long rowCount;
38 private int memoryPerPage;
39 private int memoryCount;
40
41 public PageBtreeIndex(RegularTable table, int id, String indexName, IndexColumn[] columns,
42 IndexType indexType, boolean create, Session session) {
43 initBaseIndex(table, id, indexName, columns, indexType);
44 if (!database.isStarting() && create) {
45 checkIndexColumnTypes(columns);
46 }
47 // int test;
48 // trace.setLevel(TraceSystem.DEBUG);
49 tableData = table;
50 if (!database.isPersistent() || id < 0) {
51 throw DbException.throwInternalError("" + indexName);
52 }
53 this.store = database.getPageStore();
54 store.addIndex(this);
55 if (create) {
56 // new index
57 rootPageId = store.allocatePage();
58 // TODO currently the head position is stored in the log
59 // it should not for new tables, otherwise redo of other operations
60 // must ensure this page is not used for other things
61 store.addMeta(this, session);
62 PageBtreeLeaf root = PageBtreeLeaf.create(this, rootPageId, PageBtree.ROOT);
63 store.logUndo(root, null);
64 store.update(root);
65 } else {
66 rootPageId = store.getRootPageId(id);
67 PageBtree root = getPage(rootPageId);
68 rowCount = root.getRowCount();
69 }
70 this.needRebuild = create || (rowCount == 0 && store.isRecoveryRunning());
71 if (trace.isDebugEnabled()) {
72 trace.debug("opened {0} rows: {1}", getName() , rowCount);
73 }
74 memoryPerPage = (Constants.MEMORY_PAGE_BTREE + store.getPageSize()) >> 2;
75 }
76
77 private static void checkIndexColumnTypes(IndexColumn[] columns) {
78 for (IndexColumn c : columns) {
79 int type = c.column.getType();
80 if (type == Value.CLOB || type == Value.BLOB) {
81 throw DbException.get(ErrorCode.FEATURE_NOT_SUPPORTED_1, "Index on BLOB or CLOB column: " + c.column.getCreateSQL());
82 }
83 }
84 }
85
86 public void add(Session session, Row row) {
87 if (trace.isDebugEnabled()) {
88 trace.debug("{0} add {1}", getName(), row);
89 }
90 // safe memory
91 SearchRow newRow = getSearchRow(row);
92 try {
93 addRow(newRow);
94 } finally {
95 store.incrementChangeCount();
96 }
97 }
98
99 private void addRow(SearchRow newRow) {
100 while (true) {
101 PageBtree root = getPage(rootPageId);
102 int splitPoint = root.addRowTry(newRow);
103 if (splitPoint == -1) {
104 break;
105 }
106 if (trace.isDebugEnabled()) {
107 trace.debug("split {0}", splitPoint);
108 }
109 SearchRow pivot = root.getRow(splitPoint - 1);
110 store.logUndo(root, root.data);
111 PageBtree page1 = root;
112 PageBtree page2 = root.split(splitPoint);
113 store.logUndo(page2, null);
114 int id = store.allocatePage();
115 page1.setPageId(id);
116 page1.setParentPageId(rootPageId);
117 page2.setParentPageId(rootPageId);
118 PageBtreeNode newRoot = PageBtreeNode.create(this, rootPageId, PageBtree.ROOT);
119 store.logUndo(newRoot, null);
120 newRoot.init(page1, pivot, page2);
121 store.update(page1);
122 store.update(page2);
123 store.update(newRoot);
124 root = newRoot;
125 }
126 invalidateRowCount();
127 rowCount++;
128 }
129
130 /**
131 * Create a search row for this row.
132 *
133 * @param row the row
134 * @return the search row
135 */
136 private SearchRow getSearchRow(Row row) {
137 SearchRow r = table.getTemplateSimpleRow(columns.length == 1);
138 r.setKeyAndVersion(row);
139 for (Column c : columns) {
140 int idx = c.getColumnId();
141 r.setValue(idx, row.getValue(idx));
142 }
143 return r;
144 }
145
146 /**
147 * Read the given page.
148 *
149 * @param id the page id
150 * @return the page
151 */
152 PageBtree getPage(int id) {
153 Page p = store.getPage(id);
154 if (p == null) {
155 PageBtreeLeaf empty = PageBtreeLeaf.create(this, id, PageBtree.ROOT);
156 // could have been created before, but never committed
157 store.logUndo(empty, null);
158 store.update(empty);
159 return empty;
160 } else if (!(p instanceof PageBtree)) {
161 throw DbException.get(ErrorCode.FILE_CORRUPTED_1, "" + p);
162 }
163 return (PageBtree) p;
164 }
165
166 public boolean canGetFirstOrLast() {
167 return true;
168 }
169
170 public Cursor findNext(Session session, SearchRow first, SearchRow last) {
171 return find(session, first, true, last);
172 }
173
174 public Cursor find(Session session, SearchRow first, SearchRow last) {
175 return find(session, first, false, last);
176 }
177
178 private Cursor find(Session session, SearchRow first, boolean bigger, SearchRow last) {
179 if (SysProperties.CHECK && store == null) {
180 throw DbException.get(ErrorCode.OBJECT_CLOSED);
181 }
182 PageBtree root = getPage(rootPageId);
183 PageBtreeCursor cursor = new PageBtreeCursor(session, this, last);
184 root.find(cursor, first, bigger);
185 return cursor;
186 }
187
188 public Cursor findFirstOrLast(Session session, boolean first) {
189 if (first) {
190 // TODO optimization: this loops through NULL elements
191 Cursor cursor = find(session, null, false, null);
192 while (cursor.next()) {
193 SearchRow row = cursor.getSearchRow();
194 Value v = row.getValue(columnIds[0]);
195 if (v != ValueNull.INSTANCE) {
196 return cursor;
197 }
198 }
199 return cursor;
200 }
201 PageBtree root = getPage(rootPageId);
202 PageBtreeCursor cursor = new PageBtreeCursor(session, this, null);
203 root.last(cursor);
204 cursor.previous();
205 // TODO optimization: this loops through NULL elements
206 do {
207 SearchRow row = cursor.getSearchRow();
208 if (row == null) {
209 break;
210 }
211 Value v = row.getValue(columnIds[0]);
212 if (v != ValueNull.INSTANCE) {
213 return cursor;
214 }
215 } while (cursor.previous());
216 return cursor;
217 }
218
219 public double getCost(Session session, int[] masks) {
220 return 10 * getCostRangeIndex(masks, tableData.getRowCount(session));
221 }
222
223 public boolean needRebuild() {
224 return needRebuild;
225 }
226
227 public void remove(Session session, Row row) {
228 if (trace.isDebugEnabled()) {
229 trace.debug("{0} remove {1}", getName(), row);
230 }
231 // TODO invalidate row count
232 // setChanged(session);
233 if (rowCount == 1) {
234 removeAllRows();
235 } else {
236 try {
237 PageBtree root = getPage(rootPageId);
238 root.remove(row);
239 invalidateRowCount();
240 rowCount--;
241 } finally {
242 store.incrementChangeCount();
243 }
244 }
245 }
246
247 public void remove(Session session) {
248 if (trace.isDebugEnabled()) {
249 trace.debug("remove");
250 }
251 removeAllRows();
252 store.free(rootPageId);
253 store.removeMeta(this, session);
254 }
255
256 public void truncate(Session session) {
257 if (trace.isDebugEnabled()) {
258 trace.debug("truncate");
259 }
260 removeAllRows();
261 if (tableData.getContainsLargeObject()) {
262 database.getLobStorage().removeAllForTable(table.getId());
263 }
264 tableData.setRowCount(0);
265 }
266
267 private void removeAllRows() {
268 try {
269 PageBtree root = getPage(rootPageId);
270 root.freeRecursive();
271 root = PageBtreeLeaf.create(this, rootPageId, PageBtree.ROOT);
272 store.removeRecord(rootPageId);
273 store.update(root);
274 rowCount = 0;
275 } finally {
276 store.incrementChangeCount();
277 }
278 }
279
280 public void checkRename() {
281 // ok
282 }
283
284 /**
285 * Get a row from the main index.
286 *
287 * @param session the session
288 * @param key the row key
289 * @return the row
290 */
291 public Row getRow(Session session, long key) {
292 return tableData.getRow(session, key);
293 }
294
295 PageStore getPageStore() {
296 return store;
297 }
298
299 public long getRowCountApproximation() {
300 return tableData.getRowCountApproximation();
301 }
302
303 public long getRowCount(Session session) {
304 return rowCount;
305 }
306
307 public void close(Session session) {
308 if (trace.isDebugEnabled()) {
309 trace.debug("close");
310 }
311 // can not close the index because it might get used afterwards,
312 // for example after running recovery
313 try {
314 writeRowCount();
315 } finally {
316 store.incrementChangeCount();
317 }
318 }
319
320 /**
321 * Read a row from the data page at the given offset.
322 *
323 * @param data the data
324 * @param offset the offset
325 * @param onlyPosition whether only the position of the row is stored
326 * @param needData whether the row data is required
327 * @return the row
328 */
329 SearchRow readRow(Data data, int offset, boolean onlyPosition, boolean needData) {
330 synchronized (data) {
331 data.setPos(offset);
332 long key = data.readVarLong();
333 if (onlyPosition) {
334 if (needData) {
335 return tableData.getRow(null, key);
336 }
337 SearchRow row = table.getTemplateSimpleRow(true);
338 row.setKey(key);
339 return row;
340 }
341 SearchRow row = table.getTemplateSimpleRow(columns.length == 1);
342 row.setKey(key);
343 for (Column col : columns) {
344 int idx = col.getColumnId();
345 row.setValue(idx, data.readValue());
346 }
347 return row;
348 }
349 }
350
351 /**
352 * Get the complete row from the data index.
353 *
354 * @param key the key
355 * @return the row
356 */
357 SearchRow readRow(long key) {
358 return tableData.getRow(null, key);
359 }
360
361 /**
362 * Write a row to the data page at the given offset.
363 *
364 * @param data the data
365 * @param offset the offset
366 * @param onlyPosition whether only the position of the row is stored
367 * @param row the row to write
368 */
369 void writeRow(Data data, int offset, SearchRow row, boolean onlyPosition) {
370 data.setPos(offset);
371 data.writeVarLong(row.getKey());
372 if (!onlyPosition) {
373 for (Column col : columns) {
374 int idx = col.getColumnId();
375 data.writeValue(row.getValue(idx));
376 }
377 }
378 }
379
380 /**
381 * Get the size of a row (only the part that is stored in the index).
382 *
383 * @param dummy a dummy data page to calculate the size
384 * @param row the row
385 * @param onlyPosition whether only the position of the row is stored
386 * @return the number of bytes
387 */
388 int getRowSize(Data dummy, SearchRow row, boolean onlyPosition) {
389 int rowsize = Data.getVarLongLen(row.getKey());
390 if (!onlyPosition) {
391 for (Column col : columns) {
392 Value v = row.getValue(col.getColumnId());
393 rowsize += dummy.getValueLen(v);
394 }
395 }
396 return rowsize;
397 }
398
399 public boolean canFindNext() {
400 return true;
401 }
402
403 /**
404 * The root page has changed.
405 *
406 * @param session the session
407 * @param newPos the new position
408 */
409 void setRootPageId(Session session, int newPos) {
410 store.removeMeta(this, session);
411 this.rootPageId = newPos;
412 store.addMeta(this, session);
413 store.addIndex(this);
414 }
415
416 private void invalidateRowCount() {
417 PageBtree root = getPage(rootPageId);
418 root.setRowCountStored(PageData.UNKNOWN_ROWCOUNT);
419 }
420
421 public void writeRowCount() {
422 if (SysProperties.MODIFY_ON_WRITE && rootPageId == 0) {
423 // currently creating the index
424 return;
425 }
426 PageBtree root = getPage(rootPageId);
427 root.setRowCountStored(MathUtils.convertLongToInt(rowCount));
428 }
429
430 /**
431 * Check whether the given row contains data.
432 *
433 * @param row the row
434 * @return true if it contains data
435 */
436 boolean hasData(SearchRow row) {
437 return row.getValue(columns[0].getColumnId()) != null;
438 }
439
440 int getMemoryPerPage() {
441 return memoryPerPage;
442 }
443
444 /**
445 * The memory usage of a page was changed. The new value is used to adopt
446 * the average estimated memory size of a page.
447 *
448 * @param x the new memory size
449 */
450 void memoryChange(int x) {
451 if (memoryCount < Constants.MEMORY_FACTOR) {
452 memoryPerPage += (x - memoryPerPage) / ++memoryCount;
453 } else {
454 memoryPerPage += (x > memoryPerPage ? 1 : -1) + ((x - memoryPerPage) / Constants.MEMORY_FACTOR);
455 }
456 }
457
458 /**
459 * Check if calculating the memory is required.
460 *
461 * @return true if it is
462 */
463 static boolean isMemoryChangeRequired() {
464 if (memoryChangeRequired-- <= 0) {
465 memoryChangeRequired = 10;
466 return true;
467 }
468 return false;
469 }
470
471 }
472