This is an automated email from the ASF dual-hosted git repository. sboikov pushed a commit to branch ignite-invokeAll in repository https://gitbox.apache.org/repos/asf/ignite.git
commit 7eed161402c2ccad0e2842811592fa5977d5991e Author: Sergi Vladykin <sergi.vlady...@gmail.com> AuthorDate: Sun Feb 24 18:57:10 2019 +0300 refactor --- .../cache/persistence/tree/BPlusTree.java | 46 +++++++++++++++++----- 1 file changed, 37 insertions(+), 9 deletions(-) diff --git a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/tree/BPlusTree.java b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/tree/BPlusTree.java index 3d6adf2..37d7f68 100644 --- a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/tree/BPlusTree.java +++ b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/tree/BPlusTree.java @@ -3092,7 +3092,7 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements // We should not touch the root to avoid contention on it, thus it is good idea to have it < rootLvl. gettingHighLvl = retryJustHappened ? lvl + 1 : // If the retry just happened, then we may guess that the tree was not changed much. - (lvl + rootLvl) >>> 1; // Middle point between the root and the current level. + guessHighLevel(lvl); // TODO Maybe we can have a better heuristic? } @@ -3104,6 +3104,39 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements } /** + * @param lvl Current level. + * @return Some level between the current and root. + */ + private int guessHighLevel(int lvl) { + // Middle point between the root and the current level. + return (lvl + rootLvl) >>> 1; + } + + /** + * @param lvl Current level. + * @param io Page IO. + * @param pageAddr Page address. + * @param cnt Row count. + * @return {@code true} If we need to get higher, {@code false} if we are high enough. + * @throws IgniteCheckedException If failed. + */ + private boolean jumpHigher(int lvl, BPlusIO<L> io, long pageAddr, int cnt) throws IgniteCheckedException { + assert lvl >= Math.abs(gettingHighLvl); // We should not get here until we are high enough. + + // If it is a routing page or the search row is out of bounds for this page, need to get higher. + if (cnt == 0 || compare(lvl, io, pageAddr, cnt - 1, row) < 0) { + // Jump higher: avoid moving page by page. + gettingHighLvl = guessHighLevel(lvl); + + return true; + } + + // Starting from this point we are high enough to have valid search. + gettingHigh = false; + return false; + } + + /** * @param lvl Level. * @param io Page IO. * @param pageAddr Page address. @@ -3114,14 +3147,9 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements final int findInsertionPointx(int lvl, BPlusIO<L> io, long pageAddr, int cnt) throws IgniteCheckedException { - if (gettingHigh) { - assert lvl >= Math.abs(gettingHighLvl); // We should not get here until we are high enough. - - // If it is a routing page or the search row is out of bounds for this page, need to get higher. - if (cnt == 0 || compare(lvl, io, pageAddr, cnt - 1, row) < 0) - return Integer.MIN_VALUE; // Will be ignored, we will get higher because gettingHigh flag was not reset. - - gettingHigh = false; // Starting from this point we are high enough to have valid search. + if (gettingHigh && jumpHigher(lvl, io, pageAddr, cnt)) { + // The result will be ignored, we will get higher because gettingHigh flag was not reset. + return Integer.MIN_VALUE; } int idx = findInsertionPoint(lvl, io, pageAddr, 0, cnt, row, shift);