You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@ignite.apache.org by ib...@apache.org on 2022/09/14 07:02:15 UTC
[ignite-3] branch main updated: IGNITE-17670 Implementing a sorted index B+Tree (#1075)
This is an automated email from the ASF dual-hosted git repository.
ibessonov pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/ignite-3.git
The following commit(s) were added to refs/heads/main by this push:
new a4345bd523 IGNITE-17670 Implementing a sorted index B+Tree (#1075)
a4345bd523 is described below
commit a4345bd5236f7e0a1ecb899c870e09762406f25f
Author: Kirill Tkalenko <tk...@yandex.ru>
AuthorDate: Wed Sep 14 10:02:08 2022 +0300
IGNITE-17670 Implementing a sorted index B+Tree (#1075)
---
.../pagememory/index/IndexPageIoModule.java | 9 +-
.../storage/pagememory/index/IndexPageTypes.java | 9 ++
.../pagememory/index/freelist/IndexColumns.java | 1 -
.../index/freelist/IndexColumnsFreeList.java | 1 +
.../index/freelist/ReadIndexColumnsValue.java | 2 -
.../index/freelist/io/IndexColumnsDataIo.java | 3 -
.../pagememory/index/hash/io/HashIndexTreeIo.java | 8 +-
.../storage/pagememory/index/meta/IndexMeta.java | 1 -
.../pagememory/index/meta/io/IndexMetaInnerIo.java | 3 -
.../pagememory/index/meta/io/IndexMetaLeafIo.java | 3 -
.../SortedIndexRow.java} | 37 +++++---
.../SortedIndexRowKey.java} | 31 ++++---
.../pagememory/index/sorted/SortedIndexTree.java | 103 +++++++++++++++++++++
.../index/sorted/io/SortedIndexTreeInnerIo.java | 62 +++++++++++++
.../io/SortedIndexTreeIo.java} | 73 ++++++---------
.../index/sorted/io/SortedIndexTreeLeafIo.java | 62 +++++++++++++
.../io/SortedIndexTreeMetaIo.java} | 30 +++---
17 files changed, 336 insertions(+), 102 deletions(-)
diff --git a/modules/storage-page-memory/src/main/java/org/apache/ignite/internal/storage/pagememory/index/IndexPageIoModule.java b/modules/storage-page-memory/src/main/java/org/apache/ignite/internal/storage/pagememory/index/IndexPageIoModule.java
index a00368d279..1c12b0d53c 100644
--- a/modules/storage-page-memory/src/main/java/org/apache/ignite/internal/storage/pagememory/index/IndexPageIoModule.java
+++ b/modules/storage-page-memory/src/main/java/org/apache/ignite/internal/storage/pagememory/index/IndexPageIoModule.java
@@ -29,6 +29,9 @@ import org.apache.ignite.internal.storage.pagememory.index.hash.io.HashIndexTree
import org.apache.ignite.internal.storage.pagememory.index.meta.io.IndexMetaInnerIo;
import org.apache.ignite.internal.storage.pagememory.index.meta.io.IndexMetaLeafIo;
import org.apache.ignite.internal.storage.pagememory.index.meta.io.IndexMetaTreeMetaIo;
+import org.apache.ignite.internal.storage.pagememory.index.sorted.io.SortedIndexTreeInnerIo;
+import org.apache.ignite.internal.storage.pagememory.index.sorted.io.SortedIndexTreeLeafIo;
+import org.apache.ignite.internal.storage.pagememory.index.sorted.io.SortedIndexTreeMetaIo;
/**
* {@link PageIoModule} related to {@link PageMemory} based indexes.
@@ -46,7 +49,11 @@ public class IndexPageIoModule implements PageIoModule {
// Hash index IO.
HashIndexTreeMetaIo.VERSIONS,
HashIndexTreeInnerIo.VERSIONS,
- HashIndexTreeLeafIo.VERSIONS
+ HashIndexTreeLeafIo.VERSIONS,
+ // Sorted index IO.
+ SortedIndexTreeMetaIo.VERSIONS,
+ SortedIndexTreeInnerIo.VERSIONS,
+ SortedIndexTreeLeafIo.VERSIONS
);
}
}
diff --git a/modules/storage-page-memory/src/main/java/org/apache/ignite/internal/storage/pagememory/index/IndexPageTypes.java b/modules/storage-page-memory/src/main/java/org/apache/ignite/internal/storage/pagememory/index/IndexPageTypes.java
index 1621b2af26..b4fcc4830a 100644
--- a/modules/storage-page-memory/src/main/java/org/apache/ignite/internal/storage/pagememory/index/IndexPageTypes.java
+++ b/modules/storage-page-memory/src/main/java/org/apache/ignite/internal/storage/pagememory/index/IndexPageTypes.java
@@ -41,4 +41,13 @@ public interface IndexPageTypes {
/** Hash index tree meta IO type. */
short T_HASH_INDEX_LEAF_IO = 10_002;
+
+ /** Sorted index tree meta IO type. */
+ short T_SORTED_INDEX_META_IO = 10_003;
+
+ /** Sorted index tree inner IO type. */
+ short T_SORTED_INDEX_INNER_IO = 10_004;
+
+ /** Sorted index tree meta IO type. */
+ short T_SORTED_INDEX_LEAF_IO = 10_005;
}
diff --git a/modules/storage-page-memory/src/main/java/org/apache/ignite/internal/storage/pagememory/index/freelist/IndexColumns.java b/modules/storage-page-memory/src/main/java/org/apache/ignite/internal/storage/pagememory/index/freelist/IndexColumns.java
index 803bb9940c..59af2be950 100644
--- a/modules/storage-page-memory/src/main/java/org/apache/ignite/internal/storage/pagememory/index/freelist/IndexColumns.java
+++ b/modules/storage-page-memory/src/main/java/org/apache/ignite/internal/storage/pagememory/index/freelist/IndexColumns.java
@@ -52,7 +52,6 @@ public class IndexColumns implements Storable {
* @param partitionId Partition ID.
* @param valueBuffer Value buffer.
*/
-
public IndexColumns(int partitionId, @Nullable ByteBuffer valueBuffer) {
this.partitionId = partitionId;
this.valueBuffer = valueBuffer;
diff --git a/modules/storage-page-memory/src/main/java/org/apache/ignite/internal/storage/pagememory/index/freelist/IndexColumnsFreeList.java b/modules/storage-page-memory/src/main/java/org/apache/ignite/internal/storage/pagememory/index/freelist/IndexColumnsFreeList.java
index 713fa0330d..f14244184f 100644
--- a/modules/storage-page-memory/src/main/java/org/apache/ignite/internal/storage/pagememory/index/freelist/IndexColumnsFreeList.java
+++ b/modules/storage-page-memory/src/main/java/org/apache/ignite/internal/storage/pagememory/index/freelist/IndexColumnsFreeList.java
@@ -76,6 +76,7 @@ public class IndexColumnsFreeList extends AbstractFreeList<IndexColumns> {
pageListCacheLimit,
evictionTracker
);
+
this.statHolder = statHolder;
}
diff --git a/modules/storage-page-memory/src/main/java/org/apache/ignite/internal/storage/pagememory/index/freelist/ReadIndexColumnsValue.java b/modules/storage-page-memory/src/main/java/org/apache/ignite/internal/storage/pagememory/index/freelist/ReadIndexColumnsValue.java
index 9c30911e0a..9217f4b820 100644
--- a/modules/storage-page-memory/src/main/java/org/apache/ignite/internal/storage/pagememory/index/freelist/ReadIndexColumnsValue.java
+++ b/modules/storage-page-memory/src/main/java/org/apache/ignite/internal/storage/pagememory/index/freelist/ReadIndexColumnsValue.java
@@ -24,13 +24,11 @@ import org.apache.ignite.internal.storage.pagememory.mv.RowVersion;
* Reads {@link RowVersion#value()} from page-memory.
*/
public class ReadIndexColumnsValue extends ReadPageMemoryRowValue {
- /** {@inheritDoc} */
@Override
protected int valueSizeOffsetInFirstSlot() {
return IndexColumns.SIZE_OFFSET;
}
- /** {@inheritDoc} */
@Override
protected int valueOffsetInFirstSlot() {
return IndexColumns.VALUE_OFFSET;
diff --git a/modules/storage-page-memory/src/main/java/org/apache/ignite/internal/storage/pagememory/index/freelist/io/IndexColumnsDataIo.java b/modules/storage-page-memory/src/main/java/org/apache/ignite/internal/storage/pagememory/index/freelist/io/IndexColumnsDataIo.java
index 3e107fc4c5..d80a724029 100644
--- a/modules/storage-page-memory/src/main/java/org/apache/ignite/internal/storage/pagememory/index/freelist/io/IndexColumnsDataIo.java
+++ b/modules/storage-page-memory/src/main/java/org/apache/ignite/internal/storage/pagememory/index/freelist/io/IndexColumnsDataIo.java
@@ -44,7 +44,6 @@ public class IndexColumnsDataIo extends AbstractDataPageIo<IndexColumns> {
super(IndexPageTypes.T_VALUE_VERSION_DATA_IO, ver);
}
- /** {@inheritDoc} */
@Override
protected void writeRowData(long pageAddr, int dataOff, int payloadSize, IndexColumns row, boolean newRow) {
assertPageType(pageAddr);
@@ -58,7 +57,6 @@ public class IndexColumnsDataIo extends AbstractDataPageIo<IndexColumns> {
putByteBuffer(pageAddr, dataOff + IndexColumns.VALUE_OFFSET, row.valueBuffer());
}
- /** {@inheritDoc} */
@Override
protected void writeFragmentData(IndexColumns row, ByteBuffer pageBuf, int rowOff, int payloadSize) {
assertPageType(pageBuf);
@@ -78,7 +76,6 @@ public class IndexColumnsDataIo extends AbstractDataPageIo<IndexColumns> {
}
}
- /** {@inheritDoc} */
@Override
protected void printPage(long addr, int pageSize, IgniteStringBuilder sb) {
sb.app("IndexColumnsDataIo [\n");
diff --git a/modules/storage-page-memory/src/main/java/org/apache/ignite/internal/storage/pagememory/index/hash/io/HashIndexTreeIo.java b/modules/storage-page-memory/src/main/java/org/apache/ignite/internal/storage/pagememory/index/hash/io/HashIndexTreeIo.java
index 395bbb3f05..45713cddbd 100644
--- a/modules/storage-page-memory/src/main/java/org/apache/ignite/internal/storage/pagememory/index/hash/io/HashIndexTreeIo.java
+++ b/modules/storage-page-memory/src/main/java/org/apache/ignite/internal/storage/pagememory/index/hash/io/HashIndexTreeIo.java
@@ -35,16 +35,16 @@ import org.apache.ignite.internal.storage.pagememory.index.freelist.IndexColumns
import org.apache.ignite.internal.storage.pagememory.index.freelist.ReadIndexColumnsValue;
import org.apache.ignite.internal.storage.pagememory.index.hash.HashIndexRow;
import org.apache.ignite.internal.storage.pagememory.index.hash.HashIndexRowKey;
-import org.apache.ignite.internal.storage.pagememory.index.meta.IndexMeta;
import org.apache.ignite.lang.IgniteInternalCheckedException;
/**
- * Interface for {@link IndexMeta} B+Tree-related IO.
+ * Interface for {@link HashIndexRow} B+Tree-related IO.
*
* <p>Defines a following data layout:
* <ul>
- * <li>Index ID - {@link UUID} (16 bytes);</li>
- * <li>Index root page ID - long (8 bytes).</li>
+ * <li>Index columns hash - int (4 bytes);</li>
+ * <li>Index columns link - long (6 bytes);</li>
+ * <li>Row ID - {@link UUID} (16 bytes).</li>
* </ul>
*/
public interface HashIndexTreeIo {
diff --git a/modules/storage-page-memory/src/main/java/org/apache/ignite/internal/storage/pagememory/index/meta/IndexMeta.java b/modules/storage-page-memory/src/main/java/org/apache/ignite/internal/storage/pagememory/index/meta/IndexMeta.java
index d3019d3665..be3514d928 100644
--- a/modules/storage-page-memory/src/main/java/org/apache/ignite/internal/storage/pagememory/index/meta/IndexMeta.java
+++ b/modules/storage-page-memory/src/main/java/org/apache/ignite/internal/storage/pagememory/index/meta/IndexMeta.java
@@ -56,7 +56,6 @@ public class IndexMeta {
return metaPageId;
}
- /** {@inheritDoc} */
@Override
public String toString() {
return S.toString(IndexMeta.class, this, "metaPageId", IgniteUtils.hexLong(metaPageId));
diff --git a/modules/storage-page-memory/src/main/java/org/apache/ignite/internal/storage/pagememory/index/meta/io/IndexMetaInnerIo.java b/modules/storage-page-memory/src/main/java/org/apache/ignite/internal/storage/pagememory/index/meta/io/IndexMetaInnerIo.java
index 18507991c9..c1771a2da6 100644
--- a/modules/storage-page-memory/src/main/java/org/apache/ignite/internal/storage/pagememory/index/meta/io/IndexMetaInnerIo.java
+++ b/modules/storage-page-memory/src/main/java/org/apache/ignite/internal/storage/pagememory/index/meta/io/IndexMetaInnerIo.java
@@ -41,19 +41,16 @@ public class IndexMetaInnerIo extends BplusInnerIo<IndexMeta> implements IndexMe
super(IndexPageTypes.T_INDEX_META_INNER_IO, ver, true, SIZE_IN_BYTES);
}
- /** {@inheritDoc} */
@Override
public void store(long dstPageAddr, int dstIdx, BplusIo<IndexMeta> srcIo, long srcPageAddr, int srcIdx) {
IndexMetaIo.super.store(dstPageAddr, dstIdx, srcPageAddr, srcIdx);
}
- /** {@inheritDoc} */
@Override
public void storeByOffset(long pageAddr, int off, IndexMeta row) {
IndexMetaIo.super.storeByOffset(pageAddr, off, row);
}
- /** {@inheritDoc} */
@Override
public IndexMeta getLookupRow(BplusTree<IndexMeta, ?> tree, long pageAddr, int idx) {
return getRow(pageAddr, idx);
diff --git a/modules/storage-page-memory/src/main/java/org/apache/ignite/internal/storage/pagememory/index/meta/io/IndexMetaLeafIo.java b/modules/storage-page-memory/src/main/java/org/apache/ignite/internal/storage/pagememory/index/meta/io/IndexMetaLeafIo.java
index 5314020808..ff29d29be1 100644
--- a/modules/storage-page-memory/src/main/java/org/apache/ignite/internal/storage/pagememory/index/meta/io/IndexMetaLeafIo.java
+++ b/modules/storage-page-memory/src/main/java/org/apache/ignite/internal/storage/pagememory/index/meta/io/IndexMetaLeafIo.java
@@ -41,19 +41,16 @@ public class IndexMetaLeafIo extends BplusLeafIo<IndexMeta> implements IndexMeta
super(IndexPageTypes.T_INDEX_META_LEAF_IO, ver, SIZE_IN_BYTES);
}
- /** {@inheritDoc} */
@Override
public void store(long dstPageAddr, int dstIdx, BplusIo<IndexMeta> srcIo, long srcPageAddr, int srcIdx) {
IndexMetaIo.super.store(dstPageAddr, dstIdx, srcPageAddr, srcIdx);
}
- /** {@inheritDoc} */
@Override
public void storeByOffset(long pageAddr, int off, IndexMeta row) {
IndexMetaIo.super.storeByOffset(pageAddr, off, row);
}
- /** {@inheritDoc} */
@Override
public IndexMeta getLookupRow(BplusTree<IndexMeta, ?> tree, long pageAddr, int idx) {
return getRow(pageAddr, idx);
diff --git a/modules/storage-page-memory/src/main/java/org/apache/ignite/internal/storage/pagememory/index/freelist/ReadIndexColumnsValue.java b/modules/storage-page-memory/src/main/java/org/apache/ignite/internal/storage/pagememory/index/sorted/SortedIndexRow.java
similarity index 51%
copy from modules/storage-page-memory/src/main/java/org/apache/ignite/internal/storage/pagememory/index/freelist/ReadIndexColumnsValue.java
copy to modules/storage-page-memory/src/main/java/org/apache/ignite/internal/storage/pagememory/index/sorted/SortedIndexRow.java
index 9c30911e0a..c8183d28da 100644
--- a/modules/storage-page-memory/src/main/java/org/apache/ignite/internal/storage/pagememory/index/freelist/ReadIndexColumnsValue.java
+++ b/modules/storage-page-memory/src/main/java/org/apache/ignite/internal/storage/pagememory/index/sorted/SortedIndexRow.java
@@ -15,24 +15,35 @@
* limitations under the License.
*/
-package org.apache.ignite.internal.storage.pagememory.index.freelist;
+package org.apache.ignite.internal.storage.pagememory.index.sorted;
-import org.apache.ignite.internal.pagememory.datapage.ReadPageMemoryRowValue;
-import org.apache.ignite.internal.storage.pagememory.mv.RowVersion;
+import org.apache.ignite.internal.storage.RowId;
+import org.apache.ignite.internal.storage.index.IndexRow;
+import org.apache.ignite.internal.storage.pagememory.index.freelist.IndexColumns;
/**
- * Reads {@link RowVersion#value()} from page-memory.
+ * {@link IndexRow} implementation used in the {@link SortedIndexTree}.
*/
-public class ReadIndexColumnsValue extends ReadPageMemoryRowValue {
- /** {@inheritDoc} */
- @Override
- protected int valueSizeOffsetInFirstSlot() {
- return IndexColumns.SIZE_OFFSET;
+public class SortedIndexRow extends SortedIndexRowKey {
+ /** Row id. */
+ private final RowId rowId;
+
+ /**
+ * Constructor.
+ *
+ * @param indexColumns Index columns.
+ * @param rowId Row id.
+ */
+ public SortedIndexRow(IndexColumns indexColumns, RowId rowId) {
+ super(indexColumns);
+
+ this.rowId = rowId;
}
- /** {@inheritDoc} */
- @Override
- protected int valueOffsetInFirstSlot() {
- return IndexColumns.VALUE_OFFSET;
+ /**
+ * Returns a row id of the row.
+ */
+ public RowId rowId() {
+ return rowId;
}
}
diff --git a/modules/storage-page-memory/src/main/java/org/apache/ignite/internal/storage/pagememory/index/freelist/ReadIndexColumnsValue.java b/modules/storage-page-memory/src/main/java/org/apache/ignite/internal/storage/pagememory/index/sorted/SortedIndexRowKey.java
similarity index 57%
copy from modules/storage-page-memory/src/main/java/org/apache/ignite/internal/storage/pagememory/index/freelist/ReadIndexColumnsValue.java
copy to modules/storage-page-memory/src/main/java/org/apache/ignite/internal/storage/pagememory/index/sorted/SortedIndexRowKey.java
index 9c30911e0a..e0e43996f3 100644
--- a/modules/storage-page-memory/src/main/java/org/apache/ignite/internal/storage/pagememory/index/freelist/ReadIndexColumnsValue.java
+++ b/modules/storage-page-memory/src/main/java/org/apache/ignite/internal/storage/pagememory/index/sorted/SortedIndexRowKey.java
@@ -15,24 +15,29 @@
* limitations under the License.
*/
-package org.apache.ignite.internal.storage.pagememory.index.freelist;
+package org.apache.ignite.internal.storage.pagememory.index.sorted;
-import org.apache.ignite.internal.pagememory.datapage.ReadPageMemoryRowValue;
-import org.apache.ignite.internal.storage.pagememory.mv.RowVersion;
+import org.apache.ignite.internal.storage.pagememory.index.freelist.IndexColumns;
/**
- * Reads {@link RowVersion#value()} from page-memory.
+ * Key to search for a {@link SortedIndexRow} in the {@link SortedIndexTree}.
*/
-public class ReadIndexColumnsValue extends ReadPageMemoryRowValue {
- /** {@inheritDoc} */
- @Override
- protected int valueSizeOffsetInFirstSlot() {
- return IndexColumns.SIZE_OFFSET;
+public class SortedIndexRowKey {
+ private final IndexColumns indexColumns;
+
+ /**
+ * Constructor.
+ *
+ * @param indexColumns Index columns.
+ */
+ public SortedIndexRowKey(IndexColumns indexColumns) {
+ this.indexColumns = indexColumns;
}
- /** {@inheritDoc} */
- @Override
- protected int valueOffsetInFirstSlot() {
- return IndexColumns.VALUE_OFFSET;
+ /**
+ * Returns an indexed columns value.
+ */
+ public IndexColumns indexColumns() {
+ return indexColumns;
}
}
diff --git a/modules/storage-page-memory/src/main/java/org/apache/ignite/internal/storage/pagememory/index/sorted/SortedIndexTree.java b/modules/storage-page-memory/src/main/java/org/apache/ignite/internal/storage/pagememory/index/sorted/SortedIndexTree.java
new file mode 100644
index 0000000000..a7c62da3d4
--- /dev/null
+++ b/modules/storage-page-memory/src/main/java/org/apache/ignite/internal/storage/pagememory/index/sorted/SortedIndexTree.java
@@ -0,0 +1,103 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.ignite.internal.storage.pagememory.index.sorted;
+
+import java.util.concurrent.atomic.AtomicLong;
+import org.apache.ignite.internal.pagememory.PageMemory;
+import org.apache.ignite.internal.pagememory.datapage.DataPageReader;
+import org.apache.ignite.internal.pagememory.reuse.ReuseList;
+import org.apache.ignite.internal.pagememory.tree.BplusTree;
+import org.apache.ignite.internal.pagememory.tree.io.BplusIo;
+import org.apache.ignite.internal.pagememory.util.PageLockListener;
+import org.apache.ignite.internal.storage.pagememory.index.sorted.io.SortedIndexTreeInnerIo;
+import org.apache.ignite.internal.storage.pagememory.index.sorted.io.SortedIndexTreeIo;
+import org.apache.ignite.internal.storage.pagememory.index.sorted.io.SortedIndexTreeLeafIo;
+import org.apache.ignite.internal.storage.pagememory.index.sorted.io.SortedIndexTreeMetaIo;
+import org.apache.ignite.lang.IgniteInternalCheckedException;
+import org.jetbrains.annotations.Nullable;
+
+/**
+ * {@link BplusTree} implementation for storing {@link SortedIndexRow}.
+ */
+public class SortedIndexTree extends BplusTree<SortedIndexRowKey, SortedIndexRow> {
+ /** Data page reader instance to read payload from data pages. */
+ private final DataPageReader dataPageReader;
+
+ /**
+ * Constructor.
+ *
+ * @param grpId Group ID.
+ * @param grpName Group name.
+ * @param partId Partition ID.
+ * @param pageMem Page memory.
+ * @param lockLsnr Page lock listener.
+ * @param globalRmvId Remove ID.
+ * @param metaPageId Meta page ID.
+ * @param reuseList Reuse list.
+ * @param initNew {@code True} if new tree should be created.
+ * @throws IgniteInternalCheckedException If failed.
+ */
+ public SortedIndexTree(
+ int grpId,
+ @Nullable String grpName,
+ int partId,
+ PageMemory pageMem,
+ PageLockListener lockLsnr,
+ AtomicLong globalRmvId,
+ long metaPageId,
+ @Nullable ReuseList reuseList,
+ boolean initNew
+ ) throws IgniteInternalCheckedException {
+ super("SortedIndexTree_" + grpId, grpId, grpName, partId, pageMem, lockLsnr, globalRmvId, metaPageId, reuseList);
+
+ setIos(SortedIndexTreeInnerIo.VERSIONS, SortedIndexTreeLeafIo.VERSIONS, SortedIndexTreeMetaIo.VERSIONS);
+
+ dataPageReader = new DataPageReader(pageMem, grpId, statisticsHolder());
+
+ initTree(initNew);
+ }
+
+ /**
+ * Returns a partition id.
+ */
+ public int partitionId() {
+ return partId;
+ }
+
+ /**
+ * Returns a data page reader instance to read payload from data pages.
+ */
+ public DataPageReader dataPageReader() {
+ return dataPageReader;
+ }
+
+ @Override
+ protected int compare(BplusIo<SortedIndexRowKey> io, long pageAddr, int idx, SortedIndexRowKey row)
+ throws IgniteInternalCheckedException {
+ SortedIndexTreeIo sortedIndexTreeIo = (SortedIndexTreeIo) io;
+
+ return sortedIndexTreeIo.compare(dataPageReader, partId, pageAddr, idx, row);
+ }
+
+ @Override
+ public SortedIndexRow getRow(BplusIo<SortedIndexRowKey> io, long pageAddr, int idx, Object x) throws IgniteInternalCheckedException {
+ SortedIndexTreeIo sortedIndexTreeIo = (SortedIndexTreeIo) io;
+
+ return sortedIndexTreeIo.getRow(dataPageReader, partId, pageAddr, idx);
+ }
+}
diff --git a/modules/storage-page-memory/src/main/java/org/apache/ignite/internal/storage/pagememory/index/sorted/io/SortedIndexTreeInnerIo.java b/modules/storage-page-memory/src/main/java/org/apache/ignite/internal/storage/pagememory/index/sorted/io/SortedIndexTreeInnerIo.java
new file mode 100644
index 0000000000..30c6ac0c2f
--- /dev/null
+++ b/modules/storage-page-memory/src/main/java/org/apache/ignite/internal/storage/pagememory/index/sorted/io/SortedIndexTreeInnerIo.java
@@ -0,0 +1,62 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.ignite.internal.storage.pagememory.index.sorted.io;
+
+import org.apache.ignite.internal.pagememory.io.IoVersions;
+import org.apache.ignite.internal.pagememory.tree.BplusTree;
+import org.apache.ignite.internal.pagememory.tree.io.BplusInnerIo;
+import org.apache.ignite.internal.pagememory.tree.io.BplusIo;
+import org.apache.ignite.internal.storage.pagememory.index.IndexPageTypes;
+import org.apache.ignite.internal.storage.pagememory.index.sorted.SortedIndexRowKey;
+import org.apache.ignite.internal.storage.pagememory.index.sorted.SortedIndexTree;
+import org.apache.ignite.lang.IgniteInternalCheckedException;
+
+/**
+ * {@link BplusInnerIo} implementation for {@link SortedIndexTree}.
+ */
+public class SortedIndexTreeInnerIo extends BplusInnerIo<SortedIndexRowKey> implements SortedIndexTreeIo {
+ /** I/O versions. */
+ public static final IoVersions<SortedIndexTreeInnerIo> VERSIONS = new IoVersions<>(new SortedIndexTreeInnerIo(1));
+
+ /**
+ * Constructor.
+ *
+ * @param ver Page format version.
+ */
+ protected SortedIndexTreeInnerIo(int ver) {
+ super(IndexPageTypes.T_SORTED_INDEX_INNER_IO, ver, true, SIZE_IN_BYTES);
+ }
+
+ @Override
+ public void store(long dstPageAddr, int dstIdx, BplusIo<SortedIndexRowKey> srcIo, long srcPageAddr, int srcIdx) {
+ SortedIndexTreeIo.super.store(dstPageAddr, dstIdx, srcIo, srcPageAddr, srcIdx);
+ }
+
+ @Override
+ public void storeByOffset(long pageAddr, int off, SortedIndexRowKey row) {
+ SortedIndexTreeIo.super.storeByOffset(pageAddr, off, row);
+ }
+
+ @Override
+ public SortedIndexRowKey getLookupRow(BplusTree<SortedIndexRowKey, ?> tree, long pageAddr, int idx)
+ throws IgniteInternalCheckedException {
+ SortedIndexTree sortedIndexTree = (SortedIndexTree) tree;
+
+ return getRow(sortedIndexTree.dataPageReader(), sortedIndexTree.partitionId(), pageAddr, idx);
+ }
+}
diff --git a/modules/storage-page-memory/src/main/java/org/apache/ignite/internal/storage/pagememory/index/hash/io/HashIndexTreeIo.java b/modules/storage-page-memory/src/main/java/org/apache/ignite/internal/storage/pagememory/index/sorted/io/SortedIndexTreeIo.java
similarity index 67%
copy from modules/storage-page-memory/src/main/java/org/apache/ignite/internal/storage/pagememory/index/hash/io/HashIndexTreeIo.java
copy to modules/storage-page-memory/src/main/java/org/apache/ignite/internal/storage/pagememory/index/sorted/io/SortedIndexTreeIo.java
index 395bbb3f05..9fb9437429 100644
--- a/modules/storage-page-memory/src/main/java/org/apache/ignite/internal/storage/pagememory/index/hash/io/HashIndexTreeIo.java
+++ b/modules/storage-page-memory/src/main/java/org/apache/ignite/internal/storage/pagememory/index/sorted/io/SortedIndexTreeIo.java
@@ -15,11 +15,9 @@
* limitations under the License.
*/
-package org.apache.ignite.internal.storage.pagememory.index.hash.io;
+package org.apache.ignite.internal.storage.pagememory.index.sorted.io;
-import static org.apache.ignite.internal.pagememory.util.PageUtils.getInt;
import static org.apache.ignite.internal.pagememory.util.PageUtils.getLong;
-import static org.apache.ignite.internal.pagememory.util.PageUtils.putInt;
import static org.apache.ignite.internal.pagememory.util.PageUtils.putLong;
import static org.apache.ignite.internal.pagememory.util.PartitionlessLinks.PARTITIONLESS_LINK_SIZE_BYTES;
import static org.apache.ignite.internal.pagememory.util.PartitionlessLinks.readPartitionlessLink;
@@ -33,26 +31,22 @@ import org.apache.ignite.internal.pagememory.util.PageUtils;
import org.apache.ignite.internal.storage.RowId;
import org.apache.ignite.internal.storage.pagememory.index.freelist.IndexColumns;
import org.apache.ignite.internal.storage.pagememory.index.freelist.ReadIndexColumnsValue;
-import org.apache.ignite.internal.storage.pagememory.index.hash.HashIndexRow;
-import org.apache.ignite.internal.storage.pagememory.index.hash.HashIndexRowKey;
-import org.apache.ignite.internal.storage.pagememory.index.meta.IndexMeta;
+import org.apache.ignite.internal.storage.pagememory.index.sorted.SortedIndexRow;
+import org.apache.ignite.internal.storage.pagememory.index.sorted.SortedIndexRowKey;
import org.apache.ignite.lang.IgniteInternalCheckedException;
/**
- * Interface for {@link IndexMeta} B+Tree-related IO.
+ * Interface for {@link SortedIndexRow} B+Tree-related IO.
*
* <p>Defines a following data layout:
* <ul>
- * <li>Index ID - {@link UUID} (16 bytes);</li>
- * <li>Index root page ID - long (8 bytes).</li>
+ * <li>Index columns link - long (6 bytes);</li>
+ * <li>Row ID - {@link UUID} (16 bytes).</li>
* </ul>
*/
-public interface HashIndexTreeIo {
- /** Offset of the index columns hash (4 bytes). */
- int INDEX_COLUMNS_HASH_OFFSET = 0;
-
+public interface SortedIndexTreeIo {
/** Offset of the index column link (6 bytes). */
- int INDEX_COLUMNS_LINK_OFFSET = INDEX_COLUMNS_HASH_OFFSET + Integer.BYTES;
+ int INDEX_COLUMNS_LINK_OFFSET = 0;
/** Offset of rowId's most significant bits, 8 bytes. */
int ROW_ID_MSB_OFFSET = INDEX_COLUMNS_LINK_OFFSET + PARTITIONLESS_LINK_SIZE_BYTES;
@@ -71,11 +65,11 @@ public interface HashIndexTreeIo {
int offset(int idx);
/**
- * Stores a hash index row, copied from another page.
+ * Stores a sorted index row, copied from another page.
*
* @see BplusIo#store(long, int, BplusIo, long, int)
*/
- default void store(long dstPageAddr, int dstIdx, BplusIo<HashIndexRowKey> srcIo, long srcPageAddr, int srcIdx) {
+ default void store(long dstPageAddr, int dstIdx, BplusIo<SortedIndexRowKey> srcIo, long srcPageAddr, int srcIdx) {
int dstOffset = offset(dstIdx);
int srcOffset = offset(srcIdx);
@@ -83,57 +77,50 @@ public interface HashIndexTreeIo {
}
/**
- * Stores a hash index row in the page.
+ * Stores a sorted index row in the page.
*
* @see BplusIo#storeByOffset(long, int, Object)
*/
- default void storeByOffset(long pageAddr, int off, HashIndexRowKey rowKey) {
- assert rowKey instanceof HashIndexRow;
-
- HashIndexRow hashIndexRow = (HashIndexRow) rowKey;
+ default void storeByOffset(long pageAddr, int off, SortedIndexRowKey rowKey) {
+ assert rowKey instanceof SortedIndexRow;
- putInt(pageAddr, off + INDEX_COLUMNS_HASH_OFFSET, hashIndexRow.indexColumnsHash());
+ SortedIndexRow sortedIndexRow = (SortedIndexRow) rowKey;
- writePartitionlessLink(pageAddr + off + INDEX_COLUMNS_LINK_OFFSET, hashIndexRow.indexColumns().link());
+ writePartitionlessLink(pageAddr + off + INDEX_COLUMNS_LINK_OFFSET, sortedIndexRow.indexColumns().link());
- RowId rowId = hashIndexRow.rowId();
+ RowId rowId = sortedIndexRow.rowId();
putLong(pageAddr, off + ROW_ID_MSB_OFFSET, rowId.mostSignificantBits());
putLong(pageAddr, off + ROW_ID_LSB_OFFSET, rowId.leastSignificantBits());
}
/**
- * Compare the {@link HashIndexRowKey} from the page with passed {@link HashIndexRowKey}.
+ * Compare the {@link SortedIndexRowKey} from the page with passed {@link SortedIndexRowKey}.
*
* @param pageAddr Page address.
* @param idx Element's index.
* @param rowKey Lookup index row key.
* @return Comparison result.
*/
- default int compare(DataPageReader dataPageReader, int partitionId, long pageAddr, int idx, HashIndexRowKey rowKey)
+ default int compare(DataPageReader dataPageReader, int partitionId, long pageAddr, int idx, SortedIndexRowKey rowKey)
throws IgniteInternalCheckedException {
- assert rowKey instanceof HashIndexRow;
+ assert rowKey instanceof SortedIndexRow;
- HashIndexRow hashIndexRow = (HashIndexRow) rowKey;
+ SortedIndexRow sortedIndexRow = (SortedIndexRow) rowKey;
int off = offset(idx);
- int cmp = Integer.compare(getInt(pageAddr, off + INDEX_COLUMNS_HASH_OFFSET), hashIndexRow.indexColumnsHash());
-
- if (cmp != 0) {
- return cmp;
- }
-
long link = readPartitionlessLink(partitionId, pageAddr, off + INDEX_COLUMNS_LINK_OFFSET);
- //TODO Add in-place compare in IGNITE-17536
+ //TODO Add in-place compare in IGNITE-17671
ReadIndexColumnsValue indexColumnsTraversal = new ReadIndexColumnsValue();
dataPageReader.traverse(link, indexColumnsTraversal, null);
ByteBuffer indexColumnsBuffer = ByteBuffer.wrap(indexColumnsTraversal.result());
- cmp = indexColumnsBuffer.compareTo(hashIndexRow.indexColumns().valueBuffer());
+ // TODO: IGNITE-17672 Compare by BinaryTuple
+ int cmp = indexColumnsBuffer.compareTo(sortedIndexRow.indexColumns().valueBuffer());
if (cmp != 0) {
return cmp;
@@ -141,7 +128,7 @@ public interface HashIndexTreeIo {
long rowIdMsb = getLong(pageAddr, off + ROW_ID_MSB_OFFSET);
- cmp = Long.compare(rowIdMsb, hashIndexRow.rowId().mostSignificantBits());
+ cmp = Long.compare(rowIdMsb, sortedIndexRow.rowId().mostSignificantBits());
if (cmp != 0) {
return cmp;
@@ -149,25 +136,23 @@ public interface HashIndexTreeIo {
long rowIdLsb = getLong(pageAddr, off + ROW_ID_LSB_OFFSET);
- return Long.compare(rowIdLsb, hashIndexRow.rowId().leastSignificantBits());
+ return Long.compare(rowIdLsb, sortedIndexRow.rowId().leastSignificantBits());
}
/**
- * Reads a hash index row value.
+ * Reads a sorted index row value.
*
* @param dataPageReader Data page reader instance to read payload from data pages.
* @param partitionId Partition id.
* @param pageAddr Page address.
* @param idx Element's index.
- * @return Hash index row.
+ * @return Sorted index row.
* @throws IgniteInternalCheckedException If failed to read payload from data pages.
*/
- default HashIndexRow getRow(DataPageReader dataPageReader, int partitionId, long pageAddr, int idx)
+ default SortedIndexRow getRow(DataPageReader dataPageReader, int partitionId, long pageAddr, int idx)
throws IgniteInternalCheckedException {
int off = offset(idx);
- int hash = getInt(pageAddr, off + INDEX_COLUMNS_HASH_OFFSET);
-
long link = readPartitionlessLink(partitionId, pageAddr, off + INDEX_COLUMNS_LINK_OFFSET);
ReadIndexColumnsValue indexColumnsTraversal = new ReadIndexColumnsValue();
@@ -183,6 +168,6 @@ public interface HashIndexTreeIo {
RowId rowId = new RowId(partitionId, rowIdMsb, rowIdLsb);
- return new HashIndexRow(hash, indexColumns, rowId);
+ return new SortedIndexRow(indexColumns, rowId);
}
}
diff --git a/modules/storage-page-memory/src/main/java/org/apache/ignite/internal/storage/pagememory/index/sorted/io/SortedIndexTreeLeafIo.java b/modules/storage-page-memory/src/main/java/org/apache/ignite/internal/storage/pagememory/index/sorted/io/SortedIndexTreeLeafIo.java
new file mode 100644
index 0000000000..efc7f65635
--- /dev/null
+++ b/modules/storage-page-memory/src/main/java/org/apache/ignite/internal/storage/pagememory/index/sorted/io/SortedIndexTreeLeafIo.java
@@ -0,0 +1,62 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.ignite.internal.storage.pagememory.index.sorted.io;
+
+import org.apache.ignite.internal.pagememory.io.IoVersions;
+import org.apache.ignite.internal.pagememory.tree.BplusTree;
+import org.apache.ignite.internal.pagememory.tree.io.BplusIo;
+import org.apache.ignite.internal.pagememory.tree.io.BplusLeafIo;
+import org.apache.ignite.internal.storage.pagememory.index.IndexPageTypes;
+import org.apache.ignite.internal.storage.pagememory.index.sorted.SortedIndexRowKey;
+import org.apache.ignite.internal.storage.pagememory.index.sorted.SortedIndexTree;
+import org.apache.ignite.lang.IgniteInternalCheckedException;
+
+/**
+ * {@link BplusLeafIo} implementation for {@link SortedIndexTree}.
+ */
+public class SortedIndexTreeLeafIo extends BplusLeafIo<SortedIndexRowKey> implements SortedIndexTreeIo {
+ /** I/O versions. */
+ public static final IoVersions<SortedIndexTreeLeafIo> VERSIONS = new IoVersions<>(new SortedIndexTreeLeafIo(1));
+
+ /**
+ * Constructor.
+ *
+ * @param ver Page format version.
+ */
+ protected SortedIndexTreeLeafIo(int ver) {
+ super(IndexPageTypes.T_SORTED_INDEX_LEAF_IO, ver, SIZE_IN_BYTES);
+ }
+
+ @Override
+ public void store(long dstPageAddr, int dstIdx, BplusIo<SortedIndexRowKey> srcIo, long srcPageAddr, int srcIdx) {
+ SortedIndexTreeIo.super.store(dstPageAddr, dstIdx, srcIo, srcPageAddr, srcIdx);
+ }
+
+ @Override
+ public void storeByOffset(long pageAddr, int off, SortedIndexRowKey row) {
+ SortedIndexTreeIo.super.storeByOffset(pageAddr, off, row);
+ }
+
+ @Override
+ public SortedIndexRowKey getLookupRow(BplusTree<SortedIndexRowKey, ?> tree, long pageAddr, int idx)
+ throws IgniteInternalCheckedException {
+ SortedIndexTree sortedIndexTree = (SortedIndexTree) tree;
+
+ return getRow(sortedIndexTree.dataPageReader(), sortedIndexTree.partitionId(), pageAddr, idx);
+ }
+}
diff --git a/modules/storage-page-memory/src/main/java/org/apache/ignite/internal/storage/pagememory/index/freelist/ReadIndexColumnsValue.java b/modules/storage-page-memory/src/main/java/org/apache/ignite/internal/storage/pagememory/index/sorted/io/SortedIndexTreeMetaIo.java
similarity index 50%
copy from modules/storage-page-memory/src/main/java/org/apache/ignite/internal/storage/pagememory/index/freelist/ReadIndexColumnsValue.java
copy to modules/storage-page-memory/src/main/java/org/apache/ignite/internal/storage/pagememory/index/sorted/io/SortedIndexTreeMetaIo.java
index 9c30911e0a..0a776cd7f4 100644
--- a/modules/storage-page-memory/src/main/java/org/apache/ignite/internal/storage/pagememory/index/freelist/ReadIndexColumnsValue.java
+++ b/modules/storage-page-memory/src/main/java/org/apache/ignite/internal/storage/pagememory/index/sorted/io/SortedIndexTreeMetaIo.java
@@ -15,24 +15,26 @@
* limitations under the License.
*/
-package org.apache.ignite.internal.storage.pagememory.index.freelist;
+package org.apache.ignite.internal.storage.pagememory.index.sorted.io;
-import org.apache.ignite.internal.pagememory.datapage.ReadPageMemoryRowValue;
-import org.apache.ignite.internal.storage.pagememory.mv.RowVersion;
+import org.apache.ignite.internal.pagememory.io.IoVersions;
+import org.apache.ignite.internal.pagememory.tree.io.BplusMetaIo;
+import org.apache.ignite.internal.storage.pagememory.index.IndexPageTypes;
+import org.apache.ignite.internal.storage.pagememory.index.sorted.SortedIndexTree;
/**
- * Reads {@link RowVersion#value()} from page-memory.
+ * IO routines for {@link SortedIndexTree} meta pages.
*/
-public class ReadIndexColumnsValue extends ReadPageMemoryRowValue {
- /** {@inheritDoc} */
- @Override
- protected int valueSizeOffsetInFirstSlot() {
- return IndexColumns.SIZE_OFFSET;
- }
+public class SortedIndexTreeMetaIo extends BplusMetaIo {
+ /** I/O versions. */
+ public static final IoVersions<SortedIndexTreeMetaIo> VERSIONS = new IoVersions<>(new SortedIndexTreeMetaIo(1));
- /** {@inheritDoc} */
- @Override
- protected int valueOffsetInFirstSlot() {
- return IndexColumns.VALUE_OFFSET;
+ /**
+ * Constructor.
+ *
+ * @param ver Page format version.
+ */
+ protected SortedIndexTreeMetaIo(int ver) {
+ super(IndexPageTypes.T_SORTED_INDEX_META_IO, ver);
}
}