You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@ignite.apache.org by sb...@apache.org on 2019/02/26 12:17:35 UTC
[ignite] 04/11: simplified the code and fixed routing pages handling
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 596f31af64c26c3ab4808219205e1d3691753071
Author: Sergi Vladykin <se...@gmail.com>
AuthorDate: Sun Feb 24 16:35:03 2019 +0300
simplified the code and fixed routing pages handling
---
.../cache/persistence/tree/BPlusTree.java | 70 +++++++---------------
1 file changed, 20 insertions(+), 50 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 2eba7cc..e4fa862 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
@@ -3026,18 +3026,6 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
}
/**
- * If we are not on the right edge of the page or there are no forward pages,
- * then we are high enough to have valid search from here.
- *
- * @param idx Insertion point.
- * @param cnt Row count.
- * @return {@code true} If this search result is always valid and can be used.
- */
- private boolean isValidSearch(int idx, int cnt) {
- return -idx - 1 != cnt || fwdId == 0L;
- }
-
- /**
* Marks level to get high with the next row after the current row will be processed.
*
* @param lvl Current level.
@@ -3049,6 +3037,16 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
*/
private void markHighLevelForNextRow(int lvl, BPlusIO<L> io, long pageAddr, int cnt)
throws IgniteCheckedException {
+ // This flag must always be reset at this point:
+ // it makes no sense to mark levels for the next rows while we are getting high.
+ assert !gettingHigh;
+
+ // For empty pages we do nothing: if we finalize the level we may miss better opportunities lower,
+ // on the other hand, no need to mark this level because it is just an empty routing page - we will
+ // waste resources on locking and reading it when we will get high.
+ if (cnt == 0)
+ return;
+
// If the high level is finalized we do not need to mark lower levels.
if (gettingHighLvl < 0 && lvl < -gettingHighLvl)
return;
@@ -3056,9 +3054,12 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
// Compare the next row with the rightmost row in the page (the next search row must always be greater than the current one).
// Mark the level if the rightmost row is greater or equal to the next search row.
// For all the rightmost pages with no forwards (including the root page) we always will have valid search.
+ // For empty pages we have to finalize
if (fwdId == 0L || compare(io, pageAddr, cnt - 1, nextRow) >= 0)
gettingHighLvl = lvl;
else {
+ // TODO may be compare to currently found insertion point instead of the rightmost row in the page??
+
// Because we unfinalize it after each switch to the next row.
assert gettingHighLvl >= 0: gettingHighLvl + " " + lvl;
@@ -3095,52 +3096,21 @@ 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 {
- int idx;
if (gettingHigh) {
assert lvl >= Math.abs(gettingHighLvl); // We should not get here until we are high enough.
- idx = findInsertionPointStartingFromRight(row, lvl, io, pageAddr, cnt);
+ // 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, will get higher because gettingHigh flag was not reset.
- if (isValidSearch(idx, cnt))
- gettingHigh = false;
+ gettingHigh = false; // Starting from this point we are high enough to have valid search.
}
- else
- idx = findInsertionPoint(lvl, io, pageAddr, 0, cnt, row, shift);
-
- if (nextRow != null && !gettingHigh)
- markHighLevelForNextRow(lvl, io, pageAddr, cnt);
-
- return idx;
- }
-
- /**
- * Like usual {@link #findInsertionPoint} but starting with the rightmost row instead of the middle row.
- *
- * @param searchRow Search row.
- * @param lvl Level.
- * @param io Page IO.
- * @param pageAddr Page address.
- * @param cnt Row count.
- * @return Insertion point.
- */
- final int findInsertionPointStartingFromRight(L searchRow, int lvl, BPlusIO<L> io, long pageAddr, int cnt)
- throws IgniteCheckedException {
- int idx;
- if (cnt == 0)
- idx = -1; // The page is empty, nothing to search (and need to get higher if there are forward pages).
- else {
- // Try to compare with the rightmost row before doing binary search.
- int cmp = compare(lvl, io, pageAddr, cnt - 1, searchRow);
+ int idx = findInsertionPoint(lvl, io, pageAddr, 0, cnt, row, shift);
- if (cmp > 0) // Search row is less than the last row in the page, need to do binary search.
- idx = findInsertionPoint(lvl, io, pageAddr, 0, cnt, searchRow, shift);
- else if (cmp == 0)
- idx = cnt - 1; // Search row is equal to the last row in the page.
- else
- idx = -cnt - 1; // Search row is greater than the last row in the page.
- }
+ if (nextRow != null)
+ markHighLevelForNextRow(lvl, io, pageAddr, cnt);
return idx;
}