`
pleasetojava
  • 浏览: 705392 次
  • 性别: Icon_minigender_2
  • 来自: 上海
文章分类
社区版块
存档分类
最新评论

Java实现的插入法建立B+树

阅读更多
我所实现的B+树是有关于《数据库系统实现》上的B+书算法的实现。利用插入法,我构建出了一个以long型数据作为键值,以Object型数据为指针的B+索引树。
有关我的程序的说明:
(1)元组数量的取值范围的含义是:本程序中我要生成“要建立元组数”那么多个元组(这里我用Student类代替)并写入文件。每个元组的键值是一个随机长整数(不重复),数量的取值范围其实是指“随机生成的键值的最大值”
(2)要建立的元组数顾名思义,也指代B+树的叶节点的数量(因为每个叶都存放一个指向元组的文件指针)[说明:因为我用RandomAccessFile来存储元组,所以元组的文件指针实际上是一个Long型的数字]
(3)每个节点能容纳的键数量--不懂得看看B+树的定义
(4)桶的数量:引入桶的目的是因为可能要生成很多个不重复的键值,要解决不重复的问题,传统的比较方法时间消耗非常大(O(N)的),引入适量的桶可以加快查找比较的时间。我使用HashSet作为桶,以实现快速建立多个不重复的键值。(当然,要是生成键值少的话就不需要很多桶了--关于桶的概念请查阅向关资料)
(5)文本框中的值是我测试使用的初始值,当你点“复位”的时候,将显示我们老师要求的数值
(6)“要查找的键值”指,你输入一个键值,程序将在书中寻找,并在文本框中给出查找路径(打印出所经过的节点的内容),最后给出你所输入的键值在不在者棵树中。
(7)程序在使用时一定要使用我给的bat文件打开,因为这样可以打开控制台(命令行),因为生成后的树中的键值信息和树的层次信息将在命令行显示。

有关的B+树插入知识:
插入原则上是第归的:(1)设法在适当的叶节点中为新建找到空闲空间,如果有的话,就把键值放在哪里,(2)如果在适当的叶节点中没有空间,就把该叶节点分裂成两个,并且把其中的键分到这两个新节点中,使每个新节点有一半或刚好超过一半的键。(3)某一层的节点分裂在其上一层看来相当于是要在这一较高的层次上插入一个新的键-指针对。因此,我们可以在这一较高层次上第归测试用这个插入策略:如果有空间,就插入;反之则分裂这个入节点且继续相熟的高层推进。(4)例外的情况是,如果试图插入键到跟节点中并且跟节点没有空间,就分裂跟节点成两个节点,在更上一层创建一个新的跟节点。这个新的跟节点有两个刚分裂成的节点作为他的子节点。

友情提示:我的所有代码由JB9生成,压缩包中将附工程文件。由于最近在看《重构》,所以代码中有些风格是从里面学的,但是目前还学艺不精,有点不伦不类,请见谅。我的全部代码放在我的邮箱,要用的到那里去下载,各位抱歉,不会上传图片,大家下载到程序之后就可以看到了:〉
gondam_f91@163.com 密码是012401030

如果程序有BUG,或者看官有什么好的建议,欢迎回复,或发邮件到我的邮箱,我会很乐意与你讨论的。








分享到:
评论

相关推荐

    lib_minisql.rar

    典型的小型数据库设计,实现B及B+树查找

    Java面试系列-MySQL

    为什么B+树成为主要的SQL数据库的索引实现?什么是MVCC? 说说MySQL实现MVCC的原理??什么是MVCC? MVCC,全称Multi-Version Concurrency Control,即多版本并发控制。MVCC是一种并发控制的方法,一般在数据库管理...

    BPlusTree_Java实现

    //在B树中插入叶节点///////////////////////////////////////////////////////////// public void insert(long key,Object pointer) { //找到应该插入的节点 Node theNode = search(key,root); //在叶节点中...

    wyxDBMS:使用Java实现了一个关系型数据库,DBMS数据库管理系统,可使用常用增删改改查的S​​QL语句,具有数据字典,数据索引文件,并且实现了启发式查询优化

    wyxDBMS是一个用Java实现的关系型数据库 实现功能 1,用Java语言建立数据库表。 (1)数据文件和字典文件存储结构和访问方法为按行访问,数据为字符型可直接阅读。 (2)属性的个数任意,属性的类型包括整数int,...

    精品sql资源-用Java实现的关系型数据库.zip

    1、用Java语言建立数据库表。 (1) 数据文件和字典文件存储结构和存取方法为按行存取,数据为字符型可直接阅读。 (2) 属性的个数任意,属性的类型包括整数int,字符串varchar,双精度浮点double。 (3) 表的相关...

    JAVA面试题最全集

    7.Java多态的实现(继承、重载、覆盖) 8.编码转换,怎样实现将GB2312编码的字符串转换为ISO-8859-1编码的字符串。 9.Java中访问数据库的步骤,Statement和PreparedStatement之间的区别。 10.找出下列代码可能...

    java 面试题 总结

    但通常情况下,由于Java Bean是被容器所创建(如Tomcat)的,所以Java Bean应具有一个无参的构造器,另外,通常Java Bean还要实现Serializable接口用于实现Bean的持久性。Java Bean实际上相当于微软COM模型中的本地...

    java连接数据库课程设计(1).doc

    " "完成JAVA WEB应用开发,实现B/S模式的数据库访问操作。完成SQL " "SERVER或MYSQL数据库管理系统的安装,配置,JAVA数据库访问环境的配置,Tom" "cat服务器安装配置;完成数据库表的建立,记录插入等;建立用户表...

    java应用软件程序设计

    242 实例74 实现一个简单的代理服务器 246 实例75 C/S结构的分布式运算 248 第7章 Java B/S结构编程 253 实例76 简单的Servlet程序 254 实例77 简单的留言簿 256 实例78 JSP+Java Bean的计数器 ...

    数据结构树的操作实验报告

    本演示程序用JAVA编写,完成树的生成,任意位置的插入、删除,以及遍历二叉树中的结点,查找和修改树中元素的值。 ① 输入的形式和输入值的范围:插入元素时需要输入插入的位置和元素的值;删除元素时输入删除元素的...

    h_JAVA 2应用编程150例.rar

    第7章 Java B/S结构编程 253 实例76 简单的Servlet程序 254 实例77 简单的留言簿 256 实例78 JSP+Java Bean的计数器 258 实例79 数据库查询 260 实例80 文件的上传下载 262 实例81 收发E-mail 267 实例82 B/S结构的...

    数据结构与算法.xmind

    B+树 查找节点 插入节点 删除节点 图 分类 有向图 无向图 表示方法 邻接矩阵 邻接表 遍历 深度优先搜索 广度优先搜索 哈希表 哈希函数 直接定址法 数字分析法 ...

    超级有影响力霸气的Java面试题大全文档

    但通常情况下,由于Java Bean是被容器所创建(如Tomcat)的,所以Java Bean应具有一个无参的构造器,另外,通常Java Bean还要实现Serializable接口用于实现Bean的持久性。Java Bean实际上相当于微软COM模型中的本地...

    java连接数据库课程设计.doc

    " "完成JAVA WEB应用开发,实现B/S模式的数据库访问操作。完成SQL " "SERVER或MYSQL数据库管理系统的安装,配置,JAVA数据库访问环境的配置,Tom" "cat服务器安装配置;完成数据库表的建立,记录插入等;建立用户表...

    《Java-web程序设计》教案.doc

    插入的J ava程序段可以操作数据库、重新定向网页等,以实现建立动态网页所需要的功能。 4.JSP的特点 JSP最大的优点是开发的跨平台结构,它可以运行在几乎所有的操作系统平台。 JSP的优势: 一次编写,到处运行。在...

    数据结构讲义(严蔚敏版)(含算法源码)

    了解B_树,B+树的概念和特点 知道键树(数字查找树) 哈希表的概念、特点、构造哈希表(A),计算ASL和装填因子α(C) 了解各种查找表的性能(O) 9. 内部排序 直接插入排序(A) 折半插入排序(A,P) 希尔排序(A...

Global site tag (gtag.js) - Google Analytics