HSQL 索引内部实现

HSQL使用AVL Tree来实现索引，AVL Tree有如下特性：

    * 它是一个二叉树。二叉树的每个结点有零个或1个左孩子，零个或1个右孩子，和一个父亲结点（除了根节点以外）。任何节点必须满足以下关系：左子树中每个结点都不能大于这个结点，右子树的每个结点都不能小于这个结点。因此对一个二叉树进行中序遍历，我们就得到这棵树的升序排列。
    * 它是平衡的。每个结点的左子树与右子树的高度之差不能大于2， 也就是说只能为－1，0，1。

HSQL 用类Index来代表索引，它其实就是一个AVL Tree，这个Tree的每个结点就是一个Record。在HSQL中， Index是数据查询的入口，所有数据的查询（也就是Select语句）都是通过遍历Index内部Tree来查找的，因此，HSQL会为每个表至少建立一个索引，也就是主键索引。如果一个表没有主键，HSQL会自动为这个表创建一个主键列，当然这个列是用户不可见的，并且为这个列创建索引。当没法利用其它索引时，就使用主键索引。

在HSQL1.43中，它只当查询条件为<, <=, =, >, >=并且对该列进行了索引，才会利用相应的索引。利用索引时，HSQL会建立两个条件表达式（内部用类Express来表示）eStart和 eEnd，HSQL会利用eStart在Index中找到第一个满足条件的Record，然后根据这个Record找到下一个紧邻的Record，二叉树的一个标准操作，一直到eEnd条件不满足为止。

例子，对于查询条件 “COLA = 1”，如果列COLA存在索引，HSQL会建立两个条件表达式（内部用类Express来表示）eStart和eEnd，这个条件都是“COLA ＝ 1”，因此它首先找到第一个满足这个条件Record，然后根据这个Record找到下一个Record，如果这个Record也满足条件"COLA = 1"，则继续查找一下Record，直到这个Record的COLA大于1为止（小于1是不可能的）。

对于查询条件“COLA>＝1"，eStart是“COLA ＝ 1"，eEnd为空，也就是总是满足条件。HSQL将首先找到满足条件eStart的第一个Record，然后找下一个Record，直到Tree最后一个Record.

对于查询条件“COLA>1"，eStart是“COLA > 1"，eEnd为空，HSQL将首先找到满足条件"COLA ＞ 1"的第一个Record，然后再找这个Record的所有后继 Record.

对于条件 ＜， ＜＝是类似的。

我们很容易得到在HSQL中基于主键的查询效率是O(log(N))，N是表中Record的数目。

思考：
1。AVL Tree无法对IN条件利用索引，因为它没有明确的顺序结构，不过可以将IN折成多个"="的或，这样就需要对AVL TREE搜索多次，如果IN的操作数不多的话，这个效率应该还是比全扫描要高得多。对LIKE条件，AVL Tree似乎没有多大的意义，当然也可以，比如对条件"COLA LIKE 'aaa%'"，可能肯定满足条件的Record肯定在'aaa'和'aab'之间，因此可以将它们设置为eStart和eEnd来缩小查找范围，但如果条件是"COLA LIKE '%aaa'"，应该就没辙了吧。

2。似乎同时只能利用一个索引，比如查询条件"COLA < 1 and COLB > 3"，如果对在这两列上分别有索引IndexA和IndexB，那么只能要么利用IndexA，要么利用IndexB。当然也可以同时利用两个索引，对它们的结果取交集，但这样需要扫描的Record更多。