ignite-db - ceiling remove
Project: http://git-wip-us.apache.org/repos/asf/ignite/repo Commit: http://git-wip-us.apache.org/repos/asf/ignite/commit/08cd76a6 Tree: http://git-wip-us.apache.org/repos/asf/ignite/tree/08cd76a6 Diff: http://git-wip-us.apache.org/repos/asf/ignite/diff/08cd76a6 Branch: refs/heads/ignite-db-x-10884 Commit: 08cd76a614103cbd0b331bd17c8b1f9a02cba94e Parents: b79d594 Author: S.Vladykin <[email protected]> Authored: Thu Apr 14 01:09:17 2016 +0300 Committer: S.Vladykin <[email protected]> Committed: Thu Apr 14 01:09:17 2016 +0300 ---------------------------------------------------------------------- .../cache/database/tree/BPlusTree.java | 76 +++++++++++++++----- 1 file changed, 60 insertions(+), 16 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/ignite/blob/08cd76a6/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/tree/BPlusTree.java ---------------------------------------------------------------------- diff --git a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/tree/BPlusTree.java b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/tree/BPlusTree.java index 33547bc..e3dec3d 100644 --- a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/tree/BPlusTree.java +++ b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/tree/BPlusTree.java @@ -292,8 +292,17 @@ public abstract class BPlusTree<L, T extends L> { int cnt = io.getCount(buf); int idx = findInsertionPoint(io, buf, cnt, r.row); - if (idx < 0) - return Remove.RETRY; + if (idx < 0) { + if (!r.ceil) // We've found exact match on search but now it's gone. + return Remove.RETRY; + + idx = -idx - 1; + + if (idx == cnt) // We can not remove ceiling row here. + return Remove.NOT_FOUND; + + assert idx < cnt; + } r.removed = getRow(io, buf, idx); @@ -798,8 +807,27 @@ public abstract class BPlusTree<L, T extends L> { * @return Removed row. * @throws IgniteCheckedException If failed. */ + public T removeCeil(L row) throws IgniteCheckedException { + return remove(row, true); + } + + /** + * @param row Lookup row. + * @return Removed row. + * @throws IgniteCheckedException If failed. + */ public T remove(L row) throws IgniteCheckedException { - Remove r = new Remove(row); + return remove(row, false); + } + + /** + * @param row Lookup row. + * @param ceil If we can remove ceil row when we can not find exact. + * @return Removed row. + * @throws IgniteCheckedException If failed. + */ + public T remove(L row, boolean ceil) throws IgniteCheckedException { + Remove r = new Remove(row, ceil); try { for (;;) { @@ -912,6 +940,18 @@ public abstract class BPlusTree<L, T extends L> { return res; + case Remove.NOT_FOUND: + // We are at the bottom. + assert lvl == 0: lvl; + + if (!r.ceil) { + r.finish(); + + return res; + } + + // Intentional fallthrough for ceiling remove. + case Remove.FOUND: // We must be at the bottom here, just need to remove row from the current page. assert lvl == 0 : lvl; @@ -919,17 +959,15 @@ public abstract class BPlusTree<L, T extends L> { res = removeFromLeaf(r, page, backId, fwdId); - // Finish if we don't need to do any merges. - if (res == Remove.FOUND && r.needReplaceInner == FALSE && r.needMerge == FALSE) - r.finish(); - - return res; - - case Remove.NOT_FOUND: - // We are at the bottom. - assert lvl == 0: lvl; + if (res == Remove.NOT_FOUND) { + assert r.ceil: "must be a retry if not a ceiling remove"; - r.finish(); + r.finish(); // TODO may be try to remove from forward + } + else if (res == Remove.FOUND && r.needReplaceInner == FALSE && r.needMerge == FALSE) { + // Finish if we don't need to do any merges. + r.finish(); + } return res; @@ -1753,6 +1791,9 @@ public abstract class BPlusTree<L, T extends L> { * Remove operation. */ private class Remove extends Get { + /** */ + boolean ceil; + /** We may need to lock part of the tree branch from the bottom to up for multiple levels. */ Tail<L> tail; @@ -1766,16 +1807,19 @@ public abstract class BPlusTree<L, T extends L> { T removed; /** Current page. */ - public Page page; + Page page; /** */ - public short innerIdx = Short.MIN_VALUE; + short innerIdx = Short.MIN_VALUE; /** * @param row Row. + * @param ceil If we can remove ceil row when we can not find exact. */ - public Remove(L row) { + Remove(L row, boolean ceil) { super(row); + + this.ceil = ceil; } /** {@inheritDoc} */
