ignite-db - ok
Project: http://git-wip-us.apache.org/repos/asf/ignite/repo Commit: http://git-wip-us.apache.org/repos/asf/ignite/commit/3daefaea Tree: http://git-wip-us.apache.org/repos/asf/ignite/tree/3daefaea Diff: http://git-wip-us.apache.org/repos/asf/ignite/diff/3daefaea Branch: refs/heads/ignite-db-x-10884 Commit: 3daefaea84a3db026e7cadc21b46b33f9e5f7bdb Parents: 3166aeb Author: S.Vladykin <[email protected]> Authored: Wed Apr 27 00:51:06 2016 +0300 Committer: S.Vladykin <[email protected]> Committed: Wed Apr 27 00:51:06 2016 +0300 ---------------------------------------------------------------------- .../cache/database/tree/BPlusTree.java | 54 ++--- .../processors/database/BPlusTreeSelfTest.java | 214 +++++++++++++------ 2 files changed, 179 insertions(+), 89 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/ignite/blob/3daefaea/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 b90c5b2..06649cf 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 @@ -1308,7 +1308,7 @@ public abstract class BPlusTree<L, T extends L> { case Put.NOT_FOUND: // Do insert. assert lvl == p.btmLvl : "must insert at the bottom level"; - assert p.needReplaceInner == FALSE: p.needReplaceInner; + assert p.needReplaceInner == FALSE: p.needReplaceInner + " " + lvl; // Init args. p.pageId = pageId; @@ -1746,38 +1746,42 @@ public abstract class BPlusTree<L, T extends L> { assert !isFinished(); assert tail.type == Tail.EXACT; - // Need to lock more to be able to merge. - if (needReplaceInner == TRUE || - (needMergeEmptyBranch == TRUE && (tail.down == null || tail.getCount() == 0))) - return false; + boolean mergedBranch = false; - // Can merge only if tail is not a routing page. - if (tail.getCount() > 0) { - if (needMergeEmptyBranch == TRUE) { - mergeEmptyBranch(); + if (needMergeEmptyBranch == TRUE) { + // We can't merge empty branch if tail in routing page. + if (tail.down == null || tail.getCount() == 0) + return false; // Lock the whole branch up to the first non-empty. - needMergeEmptyBranch = DONE; - } + mergeEmptyBranch(); - boolean mergeMore = mergeDown(tail); + mergedBranch = true; + needMergeEmptyBranch = DONE; + } - if (needReplaceInner == READY) { - // If we've merged empty branch then the inner key was dropped. - if (needMergeEmptyBranch != DONE) - replaceInner(); // Need to replace inner key with new max key for the left subtree. + mergeDown(tail); - needReplaceInner = DONE; - } + if (needReplaceInner == READY) { + // If we've merged empty branch right now, then the inner key was dropped. + if (!mergedBranch) + replaceInner(); // Replace inner key with new max key for the left subtree. - if (tail.getCount() == 0 && tail.lvl != 0 && getRootLevel(meta) == tail.lvl) - freePage(tail.page, tail.buf, tail.io, tail.lvl, false); // Free root. - else if (mergeMore) { - doReleaseTail(tail.down); + needReplaceInner = DONE; + } + else if (needReplaceInner == TRUE) + return false; // Lock the whole branch up to the inner key page. - tail.down = null; + if (tail.getCount() == 0 && tail.lvl != 0 && getRootLevel(meta) == tail.lvl) { + // Free root if it became empty after merge. + freePage(tail.page, tail.buf, tail.io, tail.lvl, false); + } + else if (tail.sibling != null && tail.getCount() + tail.sibling.getCount() < tail.io.getMaxCount(tail.buf)) { + // Release everything lower than tail, we've already merged this path. + doReleaseTail(tail.down); - return false; - } + tail.down = null; + + return false; // Lock and merge one level more. } releaseTail(); http://git-wip-us.apache.org/repos/asf/ignite/blob/3daefaea/modules/indexing/src/test/java/org/apache/ignite/internal/processors/database/BPlusTreeSelfTest.java ---------------------------------------------------------------------- diff --git a/modules/indexing/src/test/java/org/apache/ignite/internal/processors/database/BPlusTreeSelfTest.java b/modules/indexing/src/test/java/org/apache/ignite/internal/processors/database/BPlusTreeSelfTest.java index c2b7a0b..eebd304 100644 --- a/modules/indexing/src/test/java/org/apache/ignite/internal/processors/database/BPlusTreeSelfTest.java +++ b/modules/indexing/src/test/java/org/apache/ignite/internal/processors/database/BPlusTreeSelfTest.java @@ -58,7 +58,7 @@ public class BPlusTreeSelfTest extends GridCommonAbstractTest { private static final int CACHE_ID = 100500; /** */ - private static int MAX_ITEMS_COUNT = 0; + private static int MAX_PER_PAGE = 0; /** */ private static int CNT = 10; @@ -84,7 +84,7 @@ public class BPlusTreeSelfTest extends GridCommonAbstractTest { @Override protected void beforeTest() throws Exception { long seed = System.nanoTime(); - X.println("Test seed: " + seed); + X.println("Test seed: " + seed + "L"); TestTree.rnd = new Random(seed); @@ -105,7 +105,7 @@ public class BPlusTreeSelfTest extends GridCommonAbstractTest { @Override protected void afterTest() throws Exception { pageMem.stop(); - MAX_ITEMS_COUNT = 0; + MAX_PER_PAGE = 0; PUT_INC = 1; RMV_INC = -1; CNT = 10; @@ -115,7 +115,7 @@ public class BPlusTreeSelfTest extends GridCommonAbstractTest { * @throws IgniteCheckedException If failed. */ public void testPutRemove_1_20_mm_1() throws IgniteCheckedException { - MAX_ITEMS_COUNT = 1; + MAX_PER_PAGE = 1; CNT = 20; PUT_INC = -1; RMV_INC = -1; @@ -127,7 +127,7 @@ public class BPlusTreeSelfTest extends GridCommonAbstractTest { * @throws IgniteCheckedException If failed. */ public void testPutRemove_1_20_mm_0() throws IgniteCheckedException { - MAX_ITEMS_COUNT = 1; + MAX_PER_PAGE = 1; CNT = 20; PUT_INC = -1; RMV_INC = -1; @@ -139,7 +139,7 @@ public class BPlusTreeSelfTest extends GridCommonAbstractTest { * @throws IgniteCheckedException If failed. */ public void testPutRemove_1_20_pm_1() throws IgniteCheckedException { - MAX_ITEMS_COUNT = 1; + MAX_PER_PAGE = 1; CNT = 20; PUT_INC = 1; RMV_INC = -1; @@ -151,7 +151,7 @@ public class BPlusTreeSelfTest extends GridCommonAbstractTest { * @throws IgniteCheckedException If failed. */ public void testPutRemove_1_20_pm_0() throws IgniteCheckedException { - MAX_ITEMS_COUNT = 1; + MAX_PER_PAGE = 1; CNT = 20; PUT_INC = 1; RMV_INC = -1; @@ -163,7 +163,7 @@ public class BPlusTreeSelfTest extends GridCommonAbstractTest { * @throws IgniteCheckedException If failed. */ public void testPutRemove_1_20_pp_1() throws IgniteCheckedException { - MAX_ITEMS_COUNT = 1; + MAX_PER_PAGE = 1; CNT = 20; PUT_INC = 1; RMV_INC = 1; @@ -175,7 +175,7 @@ public class BPlusTreeSelfTest extends GridCommonAbstractTest { * @throws IgniteCheckedException If failed. */ public void testPutRemove_1_20_pp_0() throws IgniteCheckedException { - MAX_ITEMS_COUNT = 1; + MAX_PER_PAGE = 1; CNT = 20; PUT_INC = 1; RMV_INC = 1; @@ -187,7 +187,7 @@ public class BPlusTreeSelfTest extends GridCommonAbstractTest { * @throws IgniteCheckedException If failed. */ public void testPutRemove_1_20_mp_1() throws IgniteCheckedException { - MAX_ITEMS_COUNT = 1; + MAX_PER_PAGE = 1; CNT = 20; PUT_INC = -1; RMV_INC = 1; @@ -199,7 +199,7 @@ public class BPlusTreeSelfTest extends GridCommonAbstractTest { * @throws IgniteCheckedException If failed. */ public void testPutRemove_1_20_mp_0() throws IgniteCheckedException { - MAX_ITEMS_COUNT = 1; + MAX_PER_PAGE = 1; CNT = 20; PUT_INC = -1; RMV_INC = 1; @@ -212,7 +212,7 @@ public class BPlusTreeSelfTest extends GridCommonAbstractTest { * @throws IgniteCheckedException If failed. */ public void testPutRemove_2_40_mm_1() throws IgniteCheckedException { - MAX_ITEMS_COUNT = 2; + MAX_PER_PAGE = 2; CNT = 40; PUT_INC = -1; RMV_INC = -1; @@ -224,7 +224,7 @@ public class BPlusTreeSelfTest extends GridCommonAbstractTest { * @throws IgniteCheckedException If failed. */ public void testPutRemove_2_40_mm_0() throws IgniteCheckedException { - MAX_ITEMS_COUNT = 2; + MAX_PER_PAGE = 2; CNT = 40; PUT_INC = -1; RMV_INC = -1; @@ -236,7 +236,7 @@ public class BPlusTreeSelfTest extends GridCommonAbstractTest { * @throws IgniteCheckedException If failed. */ public void testPutRemove_2_40_pm_1() throws IgniteCheckedException { - MAX_ITEMS_COUNT = 2; + MAX_PER_PAGE = 2; CNT = 40; PUT_INC = 1; RMV_INC = -1; @@ -248,7 +248,7 @@ public class BPlusTreeSelfTest extends GridCommonAbstractTest { * @throws IgniteCheckedException If failed. */ public void testPutRemove_2_40_pm_0() throws IgniteCheckedException { - MAX_ITEMS_COUNT = 2; + MAX_PER_PAGE = 2; CNT = 40; PUT_INC = 1; RMV_INC = -1; @@ -260,7 +260,7 @@ public class BPlusTreeSelfTest extends GridCommonAbstractTest { * @throws IgniteCheckedException If failed. */ public void testPutRemove_2_40_pp_1() throws IgniteCheckedException { - MAX_ITEMS_COUNT = 2; + MAX_PER_PAGE = 2; CNT = 40; PUT_INC = 1; RMV_INC = 1; @@ -272,7 +272,7 @@ public class BPlusTreeSelfTest extends GridCommonAbstractTest { * @throws IgniteCheckedException If failed. */ public void testPutRemove_2_40_pp_0() throws IgniteCheckedException { - MAX_ITEMS_COUNT = 2; + MAX_PER_PAGE = 2; CNT = 40; PUT_INC = 1; RMV_INC = 1; @@ -284,7 +284,7 @@ public class BPlusTreeSelfTest extends GridCommonAbstractTest { * @throws IgniteCheckedException If failed. */ public void testPutRemove_2_40_mp_1() throws IgniteCheckedException { - MAX_ITEMS_COUNT = 2; + MAX_PER_PAGE = 2; CNT = 40; PUT_INC = -1; RMV_INC = 1; @@ -296,7 +296,7 @@ public class BPlusTreeSelfTest extends GridCommonAbstractTest { * @throws IgniteCheckedException If failed. */ public void testPutRemove_2_40_mp_0() throws IgniteCheckedException { - MAX_ITEMS_COUNT = 2; + MAX_PER_PAGE = 2; CNT = 40; PUT_INC = -1; RMV_INC = 1; @@ -304,6 +304,103 @@ public class BPlusTreeSelfTest extends GridCommonAbstractTest { doTestPutRemove(false); } + // ------- 3 - 60 + /** + * @throws IgniteCheckedException If failed. + */ + public void testPutRemove_3_60_mm_1() throws IgniteCheckedException { + MAX_PER_PAGE = 3; + CNT = 60; + PUT_INC = -1; + RMV_INC = -1; + + doTestPutRemove(true); + } + + /** + * @throws IgniteCheckedException If failed. + */ + public void testPutRemove_3_60_mm_0() throws IgniteCheckedException { + MAX_PER_PAGE = 3; + CNT = 60; + PUT_INC = -1; + RMV_INC = -1; + + doTestPutRemove(false); + } + + /** + * @throws IgniteCheckedException If failed. + */ + public void testPutRemove_3_60_pm_1() throws IgniteCheckedException { + MAX_PER_PAGE = 3; + CNT = 60; + PUT_INC = 1; + RMV_INC = -1; + + doTestPutRemove(true); + } + + /** + * @throws IgniteCheckedException If failed. + */ + public void testPutRemove_3_60_pm_0() throws IgniteCheckedException { + MAX_PER_PAGE = 3; + CNT = 60; + PUT_INC = 1; + RMV_INC = -1; + + doTestPutRemove(false); + } + + /** + * @throws IgniteCheckedException If failed. + */ + public void testPutRemove_3_60_pp_1() throws IgniteCheckedException { + MAX_PER_PAGE = 3; + CNT = 60; + PUT_INC = 1; + RMV_INC = 1; + + doTestPutRemove(true); + } + + /** + * @throws IgniteCheckedException If failed. + */ + public void testPutRemove_3_60_pp_0() throws IgniteCheckedException { + MAX_PER_PAGE = 3; + CNT = 60; + PUT_INC = 1; + RMV_INC = 1; + + doTestPutRemove(false); + } + + /** + * @throws IgniteCheckedException If failed. + */ + public void testPutRemove_3_60_mp_1() throws IgniteCheckedException { + MAX_PER_PAGE = 3; + CNT = 60; + PUT_INC = -1; + RMV_INC = 1; + + doTestPutRemove(true); + } + + /** + * @throws IgniteCheckedException If failed. + */ + public void testPutRemove_3_60_mp_0() throws IgniteCheckedException { + MAX_PER_PAGE = 3; + CNT = 60; + PUT_INC = -1; + RMV_INC = 1; + + doTestPutRemove(false); + } + /** * @param canGetRow Can get row from inner page. * @throws IgniteCheckedException If failed. @@ -346,16 +443,20 @@ public class BPlusTreeSelfTest extends GridCommonAbstractTest { /** * @throws IgniteCheckedException If failed. */ - public void _testRandomRemove0() throws IgniteCheckedException { - // seed: 1461177795261173000, 1461187841179332000 + public void testRandomRemove_1_30_0() throws IgniteCheckedException { + MAX_PER_PAGE = 1; + CNT = 30; + doTestRandomRemove(false); } /** * @throws IgniteCheckedException If failed. */ - public void _testRandomRemove1() throws IgniteCheckedException { - // seed: 1461188744119034000 1461188844311788000 1461189099834526000 + public void testRandomRemove_1_30_1() throws IgniteCheckedException { + MAX_PER_PAGE = 1; + CNT = 30; + doTestRandomRemove(true); } @@ -368,58 +469,43 @@ public class BPlusTreeSelfTest extends GridCommonAbstractTest { Map<Long,Long> map = new HashMap<>(); - int cnt = 100_000; + for (int i = 0 ; i < 100_000; i++) { + Long x = (long)tree.randomInt(CNT); - int rmv = 0; + if (i % 1000 == 0) + X.println(" --> " + i + " " + x); - for (long x = 0; x < cnt; x++) - assertEquals(map.put(x,x), tree.put(x)); - - for (;;) { - for (int i = 0; i < 1000 && !map.isEmpty();) { - Long x = (long)tree.randomInt(cnt); - - if (map.remove(x) != null) { -// if (rmv > 93440) { -// X.println("Rmv: " + rmv + " -> " + x); -// -// if (rmv == 93449) -// X.println(tree.printTree()); -// } +// if (i >= 57) +// X.println(tree.printTree()); + if (tree.randomInt(2) == 0) + assertEquals(map.put(x, x), tree.put(x)); + else { + if (map.remove(x) != null) assertEquals(x, tree.remove(x)); - assertNull(tree.remove(x)); - - rmv++; - i++; - } + assertNull(tree.remove(x)); } - GridCursor<Long> cursor = tree.find(null, null); - - int size = 0; + if (i % 100 == 0) { + GridCursor<Long> cursor = tree.find(null, null); - while (cursor.next()) { - size++; + int size = 0; - Long x = cursor.get(); + while (cursor.next()) { + size++; - assert x != null; + x = cursor.get(); - assertEquals(map.get(x), x); - } + assert x != null; - assertEquals(map.size(), size); + assertEquals(map.get(x), x); + } - if (size == 0) - break; + assertEquals(map.size(), size); + } } } - private void doTestStagedPutRemove(boolean canGetRow) { - // TODO - } - /** * @param canGetRow Can get row from inner page. * @return Test tree instance. @@ -540,8 +626,8 @@ public class BPlusTreeSelfTest extends GridCommonAbstractTest { /** {@inheritDoc} */ @Override public int getMaxCount(ByteBuffer buf) { - if (MAX_ITEMS_COUNT != 0) - return MAX_ITEMS_COUNT; + if (MAX_PER_PAGE != 0) + return MAX_PER_PAGE; return super.getMaxCount(buf); } @@ -579,8 +665,8 @@ public class BPlusTreeSelfTest extends GridCommonAbstractTest { /** {@inheritDoc} */ @Override public int getMaxCount(ByteBuffer buf) { - if (MAX_ITEMS_COUNT != 0) - return MAX_ITEMS_COUNT; + if (MAX_PER_PAGE != 0) + return MAX_PER_PAGE; return super.getMaxCount(buf); }
