- 浏览: 3291873 次
- 性别:
- 来自: 北京
文章分类
- 全部博客 (567)
- Web前端-html/表单 (19)
- Web前端-CSS (24)
- Web前端-CSS框架 (4)
- Web前端-JS语言核心 (50)
- Web前端-JS客户端 (26)
- nodejs生态+grunt (10)
- seajs和requirejs (9)
- backbone等框架 (7)
- 模板基础 (7)
- Web前端-deps(不改动) (6)
- Web前端-component (10)
- Web前端-jquery-plugin (13)
- 浏览器兼容性 (6)
- Web前端-使用jQuery (25)
- Web前端-使用jqueryui (6)
- Web前端-性能优化 (3)
- Web协议-HTTP (6)
- ExtJS (13)
- PHP (22)
- PHP面向对象 (4)
- PHP扩展-SOAP (6)
- PHP扩展-curl (4)
- PHP与HTML(导出) (5)
- PHP扩展-综合 (7)
- mysql基础应用 (18)
- 技术心情 (18)
- 算法和面试题 (17)
- 工具(开发)使用 (36)
- memcached原理 (2)
- session和cookie (4)
- UML (2)
- Web前端_FusionCharts (5)
- Web前端_Flex (4)
- Web前端_JSP (3)
- JavaSE (10)
- JavaEE (4)
- tomcat (2)
- Servlet开发 (3)
- Spring开发 (1)
- REST相关 (2)
- 大访问量、高并发 (2)
- 网络编程 (1)
- YII (21)
- linux命令和内核 (12)
- yii与数据库 (10)
- yii与表单 (12)
- yii view层 (1)
- perl (7)
- yii扩展 (7)
- shell (4)
- photoshop (7)
- 视觉设计 (2)
- 我关注的名人在路上 (4)
- 1-自学能力 (1)
- 2-人际沟通能力 (3)
- 3-职业规划能力 (7)
- 4-项目管理能力 (2)
- python (3)
- django (4)
- Mysql高级应用 (6)
- prototype.js (4)
- Web系统安全 (1)
- Web前端-mobile (2)
- egret (6)
- jQuery源码分析 (5)
- fis (4)
最新评论
-
yzq21056563:
感谢作者分享~请教下,http://www.lisa33xia ...
CSS基础:text-overflow:ellipsis溢出文本 -
u012206458:
$.ajax的error,complete,success方法 -
DEMONU:
谢谢,虽然不能给你赞助,但是要给你顶
mysql中key 、primary key 、unique key 与index区别 -
njupt_tolmes:
阿凡达阿凡达阿凡达阿凡达阿凡达阿凡达阿凡达阿凡达阿凡达阿滕庆亚 ...
CSS基础:text-overflow:ellipsis溢出文本 -
zenmshuo:
用过SpreadJS,也包含数据可视化的图表
推荐几个web中常用js图表插件
一棵m阶的B树满足下列条件:
⑴ 树中每个结点至多有m个孩子;
⑵ 除根结点和叶子结点外,其它每个结点至少有m/2个孩子;
⑶ 若根结点不是叶子结点,则至少有2个孩子;
⑷ 所有叶子结点都出现在同一层,叶子结点不包含任何关键字信息;
⑸ 有k个孩子的非终端结点恰好包含有k-1个关键字。
在B树中,每个结点中关键字从小到大排列,并且当该结点的孩子是非叶子结点时,该k-1个关键字正好是k个孩子包含的关键字的值域的分划。
因为叶子结点不包含关键字,所以可以把叶子结点看成在树里实际上并不存在外部结点,指向这些外部结点的指针为空,叶子结点的数目正好等于树中所包含的关键字总个数加1。
B树中的一个包含n个关键字,n+1个指针的结点的一般形式为: (n,P0,K1,P1,K2,P2,…,Kn,Pn)
其中,Ki为关键字,K1<K2<…<Kn, Pi 是指向包括Ki到Ki+1之间的关键字的子树的指针。
B+树
B+树是B-树的变体,也是一种多路搜索树:
1.其定义基本与B-树同,除了:
2.非叶子结点的子树指针与关键字个数相同;
3.非叶子结点的子树指针P[i],指向关键字值属于[K[i], K[i+1])的子树(B-树是开区间);
5.为所有叶子结点增加一个链指针;
6.所有关键字都在叶子结点出现;
不同于B树只适合随机检索,B+树同时支持随机检索和顺序检索,在实际中应用比较多。
各大IT公司面试常常问到的问题——海量数据问题。以前通常回答二级索引,即一级索引常驻内存,通过一级索引找到二级索引,读入内存,再通过二级索引找到最终要找的具体数据,而“索引”,一直设想的都是HASH,现在回头想来,HASH其实是不合适的。因为HASH只能提供映射,而不能提供范围信息。这个问题的正确答案应该是B树或者B+树。
所谓B树,是一棵多叉树,每一个节点(除了根)的分叉因子都不小于t,不大于2t。对根的要求较少,只要求不能大于2t,在树不为空的时候分叉因子不为1,根的灵活性是为B树在插入、删除操作时不违背B树的定义而服务的,具体操作参见算法导论第19章。每个节点x含有n[x]个关键字,这些关键字的作用是为该节点的孩子结点中的关键字划定范围,即划分了n[x]+1个范围,这样的话该节点就有n[x]+1个孩子结点。在实际应用中t通常很大,通常设计一个t的大小时应尽量使得一个节点的所有内容的大小和磁盘中的一个页相近,因为一次磁盘IO读取和写入都是以一个页为单位的,这样做就可以最大化地利用一次磁盘IO的操作。如一棵t=1000的B树,哪怕高度只有2,也可以存放1000^3=10亿以上的关键字,也就是说哪怕你有这么海量的数据,要查找、插入、删除其中的一个也只需要至多2次的磁盘IO(根节点是常驻内存的)。
具体的查找关键字k时,从根结点开始,通过线性比对当前节点的n[x]个关键字,决定要下降到该节点的哪一个孩子结点,直到找到要查找或者删除的关键字或者要插入的位置位置。
B+树是B树的变种,它在每个内节点里都只存放关键字信息,而只在叶子节点中存放存储所需的其它附属信息,这样就可以让内节点的分支因子最大化,也让树的高度尽可能的低。
B+树是一种树数据结构,常见于数据库与档案系统之中。B+树能够使资料保持有序,并拥有均匀的对数处理时间的插入和删除动作。B树的元素通常会自底向上插入,有别于多数自顶向下插入的二叉树。
发表评论
-
面试题201412——html5 本地存储
2014-12-23 14:58 733作者:zccst 一、LocalStorage 和 sess ... -
面试题201412——client DOM操作和CSS操作
2014-12-17 23:28 1625作者:zccst 一、DOM操作文档树 其实对于DOM系列 ... -
面试题201412——client 脚本化HTTP
2014-12-17 00:22 954作者:zccst Ajax的缺 ... -
面试题201412——core 小算法
2014-12-17 00:22 1059作者:zccst 给数组添加一个去重方法 计算字符串的字 ... -
面试题201412——client 事件
2014-12-17 00:23 1342作者:zccst 如何在i ... -
面试题201412——CSS
2014-12-17 00:24 754作者:zccst CSS的优先级?内联和important哪 ... -
面试题201412——HTML
2014-12-16 21:51 602作者:zccst 严格模式与混杂模式的区分?如何触发这两种模 ... -
面试题201412——杂项待整理
2014-12-16 20:28 581zccst js 1,跨域 2,eval 3 ... -
面试题201412——core this作用域
2014-12-16 17:43 1196作者:zccst 二、setTimeout与while的执 ... -
面试题201412——core 变量作用域
2014-12-16 16:32 1022作者:zccst 1,var a = b = 5; (f ... -
10亿个字符串的排序问题
2014-12-15 15:33 8zccst转载 一、问题描述 有一个大文件,里面有十亿个字符串 ... -
10亿个字符串的排序问题
2014-12-15 15:33 1498zccst转载 一、问题描述 有一个大文件,里面有十亿个字符串 ... -
删除数组中的某一个元素
2014-08-01 15:36 0作者:zccst 首先定义一个数组如果 var a = ... -
计算字符串中每个字符出现的次数
2014-08-04 18:30 2132思想原理:把字符串分割为数组,粒度为每一个字符。循环该数组,用 ... -
$("div")和getElementsByTagName("div")区别
2014-08-01 15:22 885作者:zccst <body> < ... -
程序设计模型——向导模型(Wizard model)
2012-08-28 22:39 1782程序设计模型——向导模型(Wizard model) 作者:z ... -
堆排序与快速排序的区别及js实现
2011-04-19 23:32 15121,快速排序 核心要点:1,选基础参考点;2,递归 fu ... -
几个算法或逻辑题
2011-04-15 12:59 1217作者:zccst 2014-6-14 PHP 在数值中加入千 ...
相关推荐
c语言的代码实现B+树。基于文件操作。模拟B+树的建立索引
详细介绍了B/B+树的区别和各自的操作,内容详实,通俗易懂,介绍的很清晰
B-树和B+树的C语言实现(数据结构)。
B+树实现,利用文件在硬盘上存储,具体使用说明在文档中
本文是对B+树数据结构和算法的详细介绍文档。文章详细,生动的描述了如何构建一个B+树。
B+树,源代码,java实现,B+树,B+树,源代码,java实现,B+树
B+ 树的组织结构_B+ 树的组织结构_B+ 树的组织结构_B+ 树的组织结构_B+ 树的组织结构_B+ 树的组织结构_
这个程序是swing版本的b+树的实现及演示,适合学些b+树实现方式的同学们,详细情况可以参考我的博文:http://blog.csdn.net/cdnight/article/details/10973281, 希望对大家有所帮助。
转B树,B树,B+树,B树转B树,B树,B+树,B树转B树,B树,B+树,B树
B+树的C++实现版本 用法举例: /* * @param bkSize 区块大小,及每个数据块的大小,建议与硬盘的区块大小相同(一般为512或4096),此值不能过小否则会导致初始化失败. * @param filePath b+树关联的文件位置. * @...
关于b+树操作的ppt,图解解说很明了。 网上B+树的资料不够多,这个是老师给的还不错
B+树实现源码 B+树实现源码 B+树实现源码 B+树实现源码 B+树实现源码
因为需要对大量图片做检索,所以写了一个3阶B+树(阶树可改),能够实现时间索引和速度索引文件的增删改查,方便快捷,另外根据删除功能实现对索引实现自动覆盖,当图片数达到一定数量,会根据时间线来覆盖,覆盖的...
详细讲解b+树及各种操作:插入,删除,更新等。
国外的B+树的讲义 与本站的《B+树分析》好像是一套的。
B+树索引 B+树索引 B+树索引 B+树索引 B+树索引 B+树索引
步骤为数据库文件创建一个B+树索引: (1)生成数据文件, (2)为数据库文件的属性创建B+ 树文件。 (3)给定键值,通过B+树进行查找。同时比较与直接扫描表的性能差别。(利用B+树时可根据内存大小决定放置多少层次到...
JAVA B+树的实现
之前一个资源只有B-树,这次上传的代码中添加了B+树的代码。用C++编写的,在Linux上用Gcc 4.5.1编译通过,实现了B-树和B+树的构造与删除,以及节点的查找,插入和删除。
本实验代码可以实现b+树的基本功能,对于B+树的初学者异地呢很有用!