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更多。
分享到:
相关推荐
使用hsql的文件存储的java代码简单实现,用jdk1.6,maven管理。使用时需要首先在本地建立hsql文件型数据库。
本文档是针对hSQL 数据库方面的基础学习,为了使项目组成员能够达到使用hSQL 数据库的目的。 1.2. 培训对象 开发人员 1.3. 常用词及符号说明 常用词: hsql:一种免费的跨平台的数据库系统 E:\hsqldb:表示是在dos ...
如何使用hsql数据库
收集的全部HSQL DataBase资料(HSQL DataBase-关于Java 的纯数据库)
hsql源码及在eclipse下建立其工程
HSQL数据库的安装使用.从下载,到部署系统一系列的操作清晰可见.千万不要跳过步骤.一步一步操作.
首先说一下hsqldb几个优点 <br> 1. 轻巧,只有600多K,运行速度非常快。结合Hibernate数据库无关的特性,非常适合在项目开发的时候使用。 2. 作为单元测试数据库。单元测试的时候,启动HSQLDB的file模式,...
此工具可以连接上本地hsql数据库,直接双击tool文件夹下的runManagerSwing就可以了
自己做的 日文 pentaho-bi-suite-3.0.1-GA
NULL 博文链接:https://taink.iteye.com/blog/707030
hsql数据库,体积最小的数据库,使用最方便的数据库,不用安装,解压就能用,携带方便
hsql中文文档 hsql中文文档 hsql中文文档 hsql中文文档 hsql中文文档 hsql中文文档
Hsqldb是一个开放源代码的JAVA数据库,其具有标准的SQL语法和JAVA接口,它可以自由使用和分发,非常简洁和快速的。
从网页上复制下来的,感觉挺不错的,文章中有注明出处尊重版权
This package contains the latest release 1 of HSQLDB 1.7.3 HSQLDB is a relational database engine and a set of tools written in Java. ... Documentation and license information can be found in the /doc ...
提供 数据库jdbc 驱动 下载; 包括: Oracle, sqlserver2000, sqlserver2005 ,mysql ,hsql等主流数据库驱动包
NULL 博文链接:https://zhouxianglh.iteye.com/blog/1901795
经典的java小型数据库,可以内存、单机、多机使用,非常棒
测试数据 博文链接:https://ynial.iteye.com/blog/148657