- 浏览: 3322762 次
- 性别:
- 来自: 北京
文章分类
- 全部博客 (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 765作者:zccst 一、LocalStorage 和 sess ... -
面试题201412——client DOM操作和CSS操作
2014-12-17 23:28 1663作者:zccst 一、DOM操作文档树 其实对于DOM系列 ... -
面试题201412——client 脚本化HTTP
2014-12-17 00:22 990作者:zccst Ajax的缺 ... -
面试题201412——core 小算法
2014-12-17 00:22 1093作者:zccst 给数组添加一个去重方法 计算字符串的字 ... -
面试题201412——client 事件
2014-12-17 00:23 1377作者:zccst 如何在i ... -
面试题201412——CSS
2014-12-17 00:24 784作者:zccst CSS的优先级?内联和important哪 ... -
面试题201412——HTML
2014-12-16 21:51 628作者:zccst 严格模式与混杂模式的区分?如何触发这两种模 ... -
面试题201412——杂项待整理
2014-12-16 20:28 628zccst js 1,跨域 2,eval 3 ... -
面试题201412——core this作用域
2014-12-16 17:43 1224作者:zccst 二、setTimeout与while的执 ... -
面试题201412——core 变量作用域
2014-12-16 16:32 1056作者:zccst 1,var a = b = 5; (f ... -
10亿个字符串的排序问题
2014-12-15 15:33 8zccst转载 一、问题描述 有一个大文件,里面有十亿个字符串 ... -
10亿个字符串的排序问题
2014-12-15 15:33 1539zccst转载 一、问题描述 有一个大文件,里面有十亿个字符串 ... -
删除数组中的某一个元素
2014-08-01 15:36 0作者:zccst 首先定义一个数组如果 var a = ... -
计算字符串中每个字符出现的次数
2014-08-04 18:30 2183思想原理:把字符串分割为数组,粒度为每一个字符。循环该数组,用 ... -
$("div")和getElementsByTagName("div")区别
2014-08-01 15:22 920作者:zccst <body> < ... -
程序设计模型——向导模型(Wizard model)
2012-08-28 22:39 1847程序设计模型——向导模型(Wizard model) 作者:z ... -
堆排序与快速排序的区别及js实现
2011-04-19 23:32 15751,快速排序 核心要点:1,选基础参考点;2,递归 fu ... -
几个算法或逻辑题
2011-04-15 12:59 1246作者:zccst 2014-6-14 PHP 在数值中加入千 ...
相关推荐
与B树相比,B+树的所有叶子节点都位于同一层,且叶子节点之间通过指针相互连接,这使得B+树非常适合范围查询和顺序访问。 #### 三、代码结构分析 1. **文件头注释**: - 作者:bysvking - 时间:2012年5月 - ...
**B+树详解** B+树(B Plus Tree)是一种自平衡的树数据结构,广泛应用于数据库和文件系统中,因为它能保持数据排序并提供快速的查找、插入和删除操作。这种数据结构的特点是所有数据都在叶子节点,非叶子节点只...
### B树、B+树、B-树详解 #### B树 B树是一种自平衡的树数据结构,常用于数据库和文件系统中。它保证了树的高度较低,从而提高了查找效率。 **特点:** 1. **节点度数:** 所有非叶子结点至多拥有两个儿子(Left和...
- B+树的叶子节点之间有链指针,便于全序遍历,而B树没有这个特性。 - B+树对磁盘I/O的优化更彻底,适合大容量数据存储。 6. **实际使用中的注意事项** - 文件实现B+树时,需要考虑文件的读写操作,如文件映射、...
在探讨数据库和文件系统中数据结构的高效管理时,B树和B+树的讨论是无法绕开的话题。这两种多路平衡查找树不仅在理论上具有深厚的基础,而且在实际应用中也显示出了极高的效率和可靠性。本文将详细解析B树和B+树在...
B+树是B树的一个变种,在B+树中,所有的实际数据(即key值)仅出现在叶子节点,并且所有的叶子节点形成了一个链表。非叶子节点存储的是路由值,用于在树中导航,但它们本身不是实际存储的数据。这个特性使得B+树在...
【B+树详解】 B+树,全称为“平衡多路搜索树”(Balanced Plus Tree),是一种在数据库和文件系统中广泛使用的高效数据结构,主要用于数据存储和检索。它结合了二叉查找树和链表的特点,优化了对磁盘等外存储设备的...
根据给定文件的信息,我们可以深入探讨B+树这一数据结构的关键知识点,以及它在数据库系统中的应用和特性。 ### B+树概述 B+树是一种自平衡的树数据结构,常用于实现虚拟内存、文件系统和数据库索引。它是由Rudolf...
B+树是一种广泛应用于数据库和文件系统中的数据结构,它的设计目的是为了高效地进行数据检索。本文将深入探讨B+树的插入和删除操作,帮助读者通过直观的图解理解这一复杂的概念。 首先,我们需要理解B+树的基本特征...
B-树和B+树的C语言实现(数据结构)。
B+树是一种高效的数据结构,尤其适用于大数据存储,如数据库索引。它的设计目标是减少磁盘或慢速存储设备的访问次数,因为这些设备的读写速度远低于内存。在【标题】"关于b+树的操作详细图解"和【描述】中提到的PPT...
B+树实现源码(C++) 本资源提供了B+树实现源码,用于提高读写盘区的性能。B+树是一种高效的数据结构,提供快速搜索和插入文件的方法。在JFS文件系统中,B+树用于描述文件内的逻辑字节范围和磁盘上字节范围的物理...
在IT领域,数据结构是构建高效算法的基础,而B+树作为一种自平衡的搜索树,...同时,对B+树的理解也将有助于你更好地理解和使用数据库管理系统,例如MySQL、Oracle等,它们内部的索引机制很大程度上依赖于B树或B+树。
B+树(B+ Tree)是一种自平衡的树数据结构,广泛应用于数据库系统和文件系统中,用于高效地存储和检索大量数据。它的主要特点是所有数据都存储在叶子节点上,且叶子节点之间通过指针链接,使得遍历变得更加简单。 #...
在计算机科学领域,数据结构是编程的基础,B+树作为一种高效的数据索引结构,被广泛应用于数据库和文件系统中。本文将深入探讨如何在Java环境中实现B+树,包括其基本概念、特性以及如何用Java代码来构建和操作B+树。...
在计算机科学领域,数据结构是基础且至关重要的部分,B+树作为一种自平衡的查找树,广泛应用于数据库和文件系统中。本节将详细讲解如何使用Java实现B+树,包括其基本概念、节点结构、树的构建、插入操作以及遍历方法...
标题提到的"B+树作为数据库的索引",指的是B+树这种数据结构在数据库管理中的重要应用。B+树(B Plus Tree)是一种自平衡的查找树,特别适合用于数据库和文件系统的索引存储。下面我们将深入探讨B+树的基本概念、...
B+树,作为一种高效的数据结构,广泛应用于数据库和文件系统中,主要因为它具有平衡特性,可以使得数据查找、插入和删除操作的时间复杂度保持在O(log n)级别,其中n是树中的节点数量。Java实现B+树的过程中,我们...
在计算机科学领域,数据结构是编程的基础,B+树(B-plus tree)作为一种高效的数据存储结构,被广泛应用于数据库和文件系统中。本篇将详细阐述如何使用C++语言实现B+树,以及其核心原理和操作。 B+树是一种自平衡的...