|
1
5 package org.h2.index;
6
7 import java.sql.SQLException  ;
8
9 import org.h2.engine.Constants;
10 import org.h2.engine.Session;
11 import org.h2.message.Message;
12 import org.h2.result.Row;
13 import org.h2.result.SearchRow;
14 import org.h2.store.DataPage;
15 import org.h2.store.DiskFile;
16 import org.h2.table.Column;
17 import org.h2.util.IntArray;
18 import org.h2.util.ObjectArray;
19 import org.h2.value.Value;
20
21
27 public class BtreeNode extends BtreePage {
28
29 private boolean writePos;
30 private IntArray pageChildren;
31
32 BtreeNode(BtreeIndex index, DataPage s) throws SQLException {
33 super(index);
34 int len = s.readInt();
35 int[] array = new int[len];
36 for(int i=0; i<array.length; i++) {
37 array[i] = s.readInt();
38 }
39 pageChildren = new IntArray(array);
40 pageData = index.readRowArray(s);
41 }
42
43 BtreeNode(BtreeIndex index, BtreePage left, SearchRow pivot, BtreePage right) {
44 super(index);
45 pageChildren = new IntArray();
46 pageChildren.add(left.getPos());
47 pageChildren.add(right.getPos());
48 pageData = new ObjectArray();
49 pageData.add(pivot);
50 }
51
52 BtreeNode(BtreeIndex index, IntArray pageChildren, ObjectArray pageData) {
53 super(index);
54 this.pageChildren = pageChildren;
55 this.pageData = pageData;
56 }
57
58 protected SearchRow getData(int i) throws SQLException {
59 SearchRow r = (SearchRow) pageData.get(i);
60 if(r == null) {
61 int p = pageChildren.get(i+1);
62 BtreePage page = index.getPage(p);
63 r = page.getFirst();
64 pageData.set(i, r);
65 }
66 return r;
67 }
68
69 public int add(Row newRow, Session session) throws SQLException {
70 int l = 0, r = pageData.size();
71 if (!Constants.ALLOW_EMTPY_BTREE_PAGES && pageChildren.size() == 0) {
72 throw Message.getInternalError("Empty btree page");
73 }
74 while (l < r) {
75 int i = (l + r) >>> 1;
76 SearchRow row = getData(i);
77 int comp = index.compareRows(row, newRow);
78 if(comp == 0) {
79 if(index.indexType.isUnique()) {
80 if(!index.isNull(newRow)) {
81 throw index.getDuplicateKeyException();
82 }
83 }
84 comp = index.compareKeys(row, newRow);
85 }
86 if(comp > 0) {
87 r = i;
88 } else {
89 l = i + 1;
90 }
91 }
92 int at = l;
93 BtreePage page = index.getPage(pageChildren.get(at));
94 int splitPoint = page.add(newRow, session);
95 if (splitPoint == 0) {
96 return 0;
97 }
98 SearchRow pivot = page.getData(splitPoint);
99 BtreePage page2 = page.split(session, splitPoint);
100 index.deletePage(session, this);
101 pageChildren.add(at + 1, page2.getPos());
102 pageData.add(at, pivot);
103 splitPoint = getSplitPoint();
104 if(splitPoint > 1) {
105 return splitPoint;
106 }
107 index.updatePage(session, this);
108 return 0;
109 }
110
111 public SearchRow remove(Session session, Row oldRow, int level) throws SQLException {
112 int l = 0, r = pageData.size();
113 if (!Constants.ALLOW_EMTPY_BTREE_PAGES && pageChildren.size() == 0) {
114 throw Message.getInternalError("Empty btree page");
115 }
116 int comp = 0;
117 while (l < r) {
118 int i = (l + r) >>> 1;
119 SearchRow row = getData(i);
120 comp = index.compareRows(row, oldRow);
121 if(comp == 0) {
122 comp = index.compareKeys(row, oldRow);
123 }
124 if(comp > 0) {
125 r = i;
126 } else {
127 l = i + 1;
128 }
129 }
130 int at = l;
131 BtreePage page = index.getPage(pageChildren.get(at));
133 SearchRow first = page.remove(session, oldRow, level+1);
134 if(first == null) {
135 return null;
137 }
138 if(first == oldRow) {
139 index.deletePage(session, this);
141 pageChildren.remove(at);
142 if(pageChildren.size()==0) {
143 return oldRow;
146 }
147 if(at == 0) {
148 first = getData(0);
150 pageData.remove(0);
151 } else {
152 first = null;
154 pageData.remove(at==0 ? 0 : at-1);
155 }
156 index.updatePage(session, this);
157 return first;
158 } else {
159 if(at == 0) {
161 return first;
163 } else {
164 index.deletePage(session, this);
166 pageData.set(at-1, first);
167 index.updatePage(session, this);
168 return null;
170 }
171 }
172 }
173
174 public BtreePage split(Session session, int splitPoint) throws SQLException {
175 ObjectArray data = new ObjectArray();
176 IntArray children = new IntArray();
177 splitPoint++;
178 int max = pageData.size();
179 if(Constants.CHECK && index.getDatabase().getLogIndexChanges() && !getDeleted()) {
180 throw Message.getInternalError();
182 }
183 for (int i = splitPoint; i < max; i++) {
184 data.add(getData(splitPoint));
185 children.add(getChild(splitPoint));
186 pageData.remove(splitPoint);
187 pageChildren.remove(splitPoint);
188 }
189 children.add(getChild(splitPoint));
190 pageData.remove(splitPoint-1);
191 pageChildren.remove(splitPoint);
192 BtreeNode n2 = new BtreeNode(index, children, data);
193 index.updatePage(session, this);
194 index.addPage(session, n2);
195 return n2;
196 }
197
198 int getChild(int i) {
199 return pageChildren.get(i);
200 }
201
202 public boolean findFirst(BtreeCursor cursor, SearchRow compare) throws SQLException {
203 int l = 0, r = pageData.size();
204 if (!Constants.ALLOW_EMTPY_BTREE_PAGES && pageChildren.size() == 0) {
205 throw Message.getInternalError("Empty btree page");
206 }
207 while (l < r) {
208 int i = (l + r) >>> 1;
209 SearchRow row = getData(i);
210 int comp = index.compareRows(row, compare);
211 if(comp >= 0) {
212 r = i;
213 } else {
214 l = i + 1;
215 }
216 }
217 if(l>=pageData.size()) {
218 BtreePage page = index.getPage(pageChildren.get(l));
219 cursor.push(this, l);
220 boolean result = page.findFirst(cursor, compare);
221 if(result) {
222 return true;
223 }
224 cursor.pop();
225 return false;
226 }
227 BtreePage page = index.getPage(pageChildren.get(l));
228 cursor.push(this, l);
229 if(page.findFirst(cursor, compare)) {
230 return true;
231 }
232 cursor.pop();
233 int i=l+1;
234 for (; i < pageData.size(); i++) {
235 SearchRow row = getData(i);
236 int comp = index.compareRows(row, compare);
237 if (comp >=0) {
238 page = index.getPage(pageChildren.get(i));
239 cursor.push(this, i);
240 if(page.findFirst(cursor, compare)) {
241 return true;
242 }
243 cursor.pop();
244 }
245 }
246 page = index.getPage(pageChildren.get(i));
247 cursor.push(this, i);
248 boolean result = page.findFirst(cursor, compare);
249 if(result) {
250 return true;
251 }
252 cursor.pop();
253 return false;
254 }
255
256 public void next(BtreeCursor cursor, int i) throws SQLException {
257 i++;
258 if (i <= pageData.size()) {
259 cursor.setStackPosition(i);
260 BtreePage page = index.getPage(pageChildren.get(i));
261 page.first(cursor);
262 return;
263 }
264 nextUpper(cursor);
265 }
266
267 private void nextUpper(BtreeCursor cursor) throws SQLException {
268 cursor.pop();
269 BtreePosition upper = cursor.pop();
270 if (upper == null) {
271 cursor.setCurrentRow(Cursor.POS_NO_ROW);
272 } else {
273 cursor.push(upper.page, upper.position);
274 upper.page.next(cursor, upper.position);
275 }
276 }
277
278 public void first(BtreeCursor cursor) throws SQLException {
279 cursor.push(this, 0);
280 BtreePage page = index.getPage(pageChildren.get(0));
281 page.first(cursor);
282 }
283
284 public void prepareWrite() throws SQLException {
285 if(getRealByteCount() >= DiskFile.BLOCK_SIZE*BLOCKS_PER_PAGE) {
286 writePos = true;
287 } else {
288 writePos = false;
289 }
290 }
291
292 public void write(DataPage buff) throws SQLException {
293 buff.writeByte((byte)'N');
294 int len = pageChildren.size();
295 buff.writeInt(len);
296 for (int i = 0; i < len; i++) {
297 buff.writeInt(pageChildren.get(i));
298 }
299 len = pageData.size();
300 buff.writeInt(len);
301 Column[] columns = index.getColumns();
302 for (int i = 0; i < len; i++) {
303 if(writePos) {
304 buff.writeInt(-1);
305 } else {
306 SearchRow row = getData(i);
307 buff.writeInt(row.getPos());
308 for (int j = 0; j < columns.length; j++) {
309 Value v = row.getValue(columns[j].getColumnId());
310 buff.writeValue(v);
311 }
312 }
313 }
314 if(buff.length() > BtreePage.BLOCKS_PER_PAGE*DiskFile.BLOCK_SIZE) {
315 throw Message.getInternalError("indexed data overflow");
316 }
317 }
318
319 int getRealByteCount() throws SQLException {
320 DataPage dummy = index.getDatabase().getDataPage();
321 int len = pageChildren.size();
322 int size = 2 + dummy.getIntLen() + dummy.getIntLen() * len;
323 len = pageData.size();
324 size += dummy.getIntLen();
325 size += len * dummy.getIntLen();
326 for (int i = 0; i < len; i++) {
327 SearchRow row = getData(i);
328 size += getRowSize(dummy, row);
329 }
330 return size + index.getRecordOverhead();
331 }
332
333 SearchRow getLast() throws SQLException {
334 if (!Constants.ALLOW_EMTPY_BTREE_PAGES && pageChildren.size() == 0) {
335 throw Message.getInternalError("Empty btree page");
336 }
337 for(int i=pageChildren.size()-1; i>=0; i--) {
338 BtreePage page = index.getPage(pageChildren.get(i));
339 if(page != null) {
340 return page.getLast();
341 }
342 }
343 return null;
344 }
345
346 SearchRow getFirst() throws SQLException {
347 for(int i=0; i<pageChildren.size(); i++) {
348 BtreePage page = index.getPage(pageChildren.get(i));
349 if(page != null) {
350 return page.getFirst();
351 }
352 }
353 return null;
354 }
355
356 public String print(String indent) throws SQLException {
357 System.out.println(indent + "node");
358 String first = null;
359 String last = null;
360 for(int i=0; i<pageChildren.size(); i++) {
361 String firstnow = index.getPage(pageChildren.get(i)).print(indent + " ");
362 if(first == null) {
363 first = firstnow;
364 }
365 if(last != null && !last.equals(firstnow)) {
366 System.out.println("STOP!!! " + last + " firstnow:" + firstnow);
367 }
368 if(i<pageData.size()) {
369 String now = getData(i).getValue(1).getString().substring(4150);
370 System.out.println(indent + " " + now);
371 last = now;
372 }
373 }
374 return first;
375 }
376
377 }
378 |
Popular Tags |
Java API By Example, From Geeks To Geeks.