(HSQL三)索引结构详解
从前面的hsql文章我们知道了hsql是怎么实现一些概念的。其中的索引在工作中最常见，我先从理论开始讲下索引都有那些类型，后面再通过源码看看hsql是如何实现索引的。
最常用的索引结构B-树.
一、索引类型:
1.顺序文件，对关系中的元组按主键进行排序面生成的文件。
2.稠密索引，简单来说就是索引里有每行记录的指针,如下图
3.稀疏索引：只为数据文件的每个存储块生成一个键-指针对，它比稠密索引节省了更多的存储空间，但查找给定值的记录需要更多的时间。
4.多级索引
5.辅助索引，我们常用的索引。
二、B-树
B+树是B-树的变体。先了解下存储块是什么：
数据库一般使用存储块来组织数据。
B-树的特点:
1.B-树能自动地保持与数据文件大小相适应的索引层次
2.对所使用的存储块空间进行管理，使每个块的充满程序在半满与全满之间。
每个存储块存放n个查找键值和n+1个指针,在存储块能容纳n个键和n+1个指针的前提下，我们把n取得尽可能大。
下面几条重要的规则限制B-树的存储块中能出现的东西：
1.叶结点中的键是数据文件中的键的拷贝，这些键以排好的序的形式，从左到右分布在叶结点中。
2.根结点中至少有两个指针被使用。所有指针指向位于B-树下一层的存储块。
3.叶结点中，最后一个指针指向它右边的下一个叶结点存储块，即指向下一个键值大于它的块。在叶块的其他n个指针当中，至少有[(n+1)/2]个指针被使用且指向数据记录;未使用的指针可看作空指针且不指向任何地方。如果第i个指针被使用,则指向具有第i个键值的记录。
4.在内层结点中,所有的n+1个指针都可以用来指向B-树中下一层的块。它们中至少[(n+1)/2]个指针真正使用（但如果是根结点，则不管n多大都只要求至少两个指针被使用)。如果j个指针被使用，那该块中将有j-1个键，设为K1,K2,...,K-1. 第一个指针指向B-树的一部分，一些键值小于K1的记录可在这一部分找到。第二个指针指向B-树的另一部分，所有的键值等于K1且小于K2的记录可在这一部分......。依此类推。最后，第j个指针指向B-树的又一部分，一些键值大于等于Kj-1的记录可以在这一部分中找到。注意：某些键值远小于K1或远大于Kj-1的记录可能根本无法通过该块到达，但可通过同一层的其他块到达。
5.所有被使用的键和指针通常都存放在数据块的开头位置，叶结点第(n+1)个指针是个例外，它用来指向下一个叶结点。
整棵树:
注意第三层的箭头指向的是块的指针，并非最小单元格。
带重复键的B-树:
注意，这里的中间块的键的定义有些变化。如果内部结点的键为K1,K2,...Kn,那么Ki将会是从第i+1个指针所能访问的子树中出现的最小新键。这里的"新",我们是指在树中第i+1个指针所指向的子树以左没有出现过Ki,但Ki在第i+1个指针指向的子树中至少出现一次。
就是说，比如上面的17键，不是最小的，但是最新的中的最小的，所以中间指针指向了17所在的第三个叶块。37同理。
B-树的查询:从左到右查内部结点，从根结点开始递归向下查键所在的范围结点，直到叶结点(块),再从左到右直到等于或大于查找键终止。
B-树的插入:
1.我们设法在适当的叶结点中为新键找到空闲空间，如果有的话，我们就把键放在那里。
2.如果在适当的叶结点中没有空间，我们就把该叶结点分裂成两个并且把其中的键分到这两个新结点中，使每个新结点有一半或刚好超过一半的键。
3.某一层的结点分裂在其上一层看来，相当于是要在这一较高的层次上插入一个新的键-指针对。因此，我们可以在这一较高层次上递归地使用这个插入策略：如果有空间，则插入；如果没有，则分裂这个父结点且继续向树的高层推进。
4.例外的情况是，如果我们试图插入键到根结点中并且根结点没有空间，那么我们就分裂根结点成两个结点且在更上一层创建一个新的根结点，这个新的根结点有两个刚分裂成的结点作为他的子结点。回想一下，不管n(结点中键的槽数)多大，根结点总是允许只有一个键和两个子结点。
下面调试看一下hsql1.6的索引结构:
从前面课程知道了索引本身的结构如下:
public class Index {
private String sName;
private int iFields;
private int iColumn[];
private int iType[];
private boolean bUnique; // just for scripting; all indexes are made unique
private Node root;
private int iColumn_0, iType_0; // just for tuning
private static int iNeedCleanUp;
}
root是值索引值的根结点,Node树结构如下:
public class Node {
int iBalance; // currently, -2 means 'deleted'
int iLeft, iRight, iParent;
Node nLeft, nRight, nParent;
private int iId; // id of index this table
Node nNext; // node of next index (nNext==null || nNext.iId=iId+1)
Row rData;
}
当test表只有一列id,数据为1,2,3,4时,如下图:
我们打断点调试，可以查看到运行时，索引根结点是id=2,而左子树是id=1,左子树没有孩子了。
要注意的是hsql1.6等早期版本的索引是二叉树。
但在hsql2.2等较新版本用的就是比较先进的二叉排序平衡树(IndexAVL)了。可以在源码中在索引的insert方法中(hsql1.6)加打印树结构的代码查看。如下:
private List<Node> nextLevel(List<Node> parentNodeList){
List<Node> curList=new ArrayList<Node>();
for(Node n:parentNodeList) {
if(n!=null) {
curList.add(n.nLeft);
curList.add(n.nRight);
}
}
return curList;
}
private void printOneNodeLine(Node n) {
if(n==null) {
System.out.println("node:null");
}else {
try {
System.out.print("node:"+n.getData()[0]);
System.out.print(" left:"+(n.getLeft()==null?"null":n.getLeft().getData()[0]));
System.out.print(" right:"+(n.getRight()==null?"null":n.getRight().getData()[0]));
System.out.println();
}catch(Exception e) {
e.printStackTrace();
}
}
}
private void printNode(Node i) {
try {
System.out.println("insert node:"+i.getData()[0]);
System.out.println("---------------start------------");
printOneNodeLine(root);
List<Node> nodeList=nextLevel(Arrays.asList(root));
while(nodeList.size()>0) {
for(Node node:nodeList) {
printOneNodeLine(node);
}
nodeList=nextLevel(nodeList);
}
System.out.println("----------end-----------");
}catch(Exception e) {
e.printStackTrace();
}
}
评论: