如何按照最左原则和B+树设计的联合索引
import java.util.ArrayList;
import java.util.List;
// 模拟数据库中的数据行
class TableRow {
int colA; // 第一列
int colB; // 第二列
int colC; // 第三列
String data;
public TableRow(int colA, int colB, int colC, String data) {
this.colA = colA;
this.colB = colB;
this.colC = colC;
this.data = data;
}
@Override
public String toString() {
return "A: " + colA + ", B: " + colB + ", C: " + colC + ", Data: " + data;
}
}
// 模拟联合索引的 B+ 树节点
class BPlusTreeNode {
boolean isLeaf;
List<Integer> keysA; // 第一列的索引（最左列）
List<Integer> keysB; // 第二列的索引
List<Integer> keysC; // 第三列的索引
List<TableRow> rowData;
public BPlusTreeNode(boolean isLeaf) {
this.isLeaf = isLeaf;
this.keysA = new ArrayList<>();
this.keysB = new ArrayList<>();
this.keysC = new ArrayList<>();
this.rowData = new ArrayList<>();
}
// 插入到叶子节点中
public void insert(int colA, int colB, int colC, TableRow row) {
keysA.add(colA);
keysB.add(colB);
keysC.add(colC);
rowData.add(row);
}
}
// 联合索引的 B+ 树
class BPlusTree {
BPlusTreeNode root;
public BPlusTree() {
// 初始化一个空的 B+ 树根节点
root = new BPlusTreeNode(true);
}
// 插入数据行到 B+ 树
public void insert(int colA, int colB, int colC, TableRow row) {
BPlusTreeNode leafNode = root;
leafNode.insert(colA, colB, colC, row);
}
// 根据联合索引查找数据行，应用最左原则
public List<TableRow> search(Integer colA, Integer colB, Integer colC) {
List<TableRow> result = new ArrayList<>();
BPlusTreeNode currentNode = root;
// 应用最左原则，必须从 colA 开始
for (int i = 0; i < currentNode.keysA.size(); i++) {
boolean match = true;
// 如果 colA 不为空，则要求匹配 A 列
if (colA != null && !currentNode.keysA.get(i).equals(colA)) {
match = false;
}
// 如果 colB 不为空且 colA 匹配，则要求匹配 B 列
if (colB != null && match && !currentNode.keysB.get(i).equals(colB)) {
match = false;
}
// 如果 colC 不为空且前两列匹配，则要求匹配 C 列
if (colC != null && match && !currentNode.keysC.get(i).equals(colC)) {
match = false;
}
// 如果匹配则将该数据行加入结果中
if (match) {
result.add(currentNode.rowData.get(i));
}
}
return result;
}
}
// 模拟表类，创建数据行和联合索引
class Table {
List<TableRow> rows;
BPlusTree index;
public Table() {
this.rows = new ArrayList<>();
this.index = new BPlusTree();
}
// 添加数据行并更新联合索引
public void addRow(int colA, int colB, int colC, String data) {
TableRow newRow = new TableRow(colA, colB, colC, data);
rows.add(newRow);
index.insert(colA, colB, colC, newRow); // 插入到索引中
}
// 根据索引查找数据，必须遵循最左原则
public List<TableRow> findByIndex(Integer colA, Integer colB, Integer colC) {
return index.search(colA, colB, colC);
}
}
public class BPlusTreeExample {
public static void main(String[] args) {
// 创建表并插入数据
Table myTable = new Table();
myTable.addRow(1, 10, 100, "Row 1");
myTable.addRow(2, 20, 200, "Row 2");
myTable.addRow(1, 30, 300, "Row 3");
myTable.addRow(2, 20, 400, "Row 4");
// 根据联合索引查找数据
System.out.println("Search (1, null, null):");
List<TableRow> result1 = myTable.findByIndex(1, null, null);
result1.forEach(System.out::println);
System.out.println("\nSearch (2, 20, null):");
List<TableRow> result2 = myTable.findByIndex(2, 20, null);
result2.forEach(System.out::println);
System.out.println("\nSearch (1, 30, 300):");
List<TableRow> result3 = myTable.findByIndex(1, 30, 300);
result3.forEach(System.out::println);
System.out.println("\nSearch (null, 20, 200): (Should return nothing due to the left-most rule)");
List<TableRow> result4 = myTable.findByIndex(null, 20, 200);
result4.forEach(System.out::println);
}
}