⑴ 如何在磁盘上以文件形式存储一棵树
参考以下代码： #include <stdio.h> //定义二叉树的存储结构 struct BTNode { char data; BTNode* lchild; BTNode* rchild; }BTNode; void Ctree(struct BTNode* t,char A[],int i) { if(t!=NULL) { A[i]=t->data; Ctree(t->lchild,A,i*2); Ctree(t->rchild,A,i*2+1); } else { A[i]=' '; } } int main(void) { //建立二叉链表存储结构的二叉树,以p1为根节点，p2,p3分别为p1的左右子树，p4为p3的左子树 struct BTNode p1,p2,p3,p4; struct BTNode *t=&p1; p1.data='a'; p2.data='b'; p3.data='c'; p4.data='d'; p1.lchild=&p2; p1.rchild=&p3; p2.lchild=NULL; p2.rchild=NULL; p3.lchild=&p4; p3.rchild=NULL; p4.lchild=NULL; p4.rchild=NULL; char A[20]={NULL}; //定义字符数组存储转换后的二叉树存储结构 Ctree(t,A,1); //调用上述转换算法 //显示结果 printf("以下是转换后数组的值：\n"); for(int i=1;i<20;i++) { if(A[i]!=NULL) printf("A[%d]=%c\n",i,A[i]); } return 0; }
⑵ 怎么用fwrite把一个二叉树存到磁盘下次用呢 我这个怎么不行 c语言
二叉树是一种数据结构，不是数据，头指针HEAD只是一个内存地址，写入磁盘有啥用，二叉树的程序终止以后，所占用的内存要释放回收，二叉树中的数据全部消失了。
如果是保留二叉树中的数据，那很简单了，遍历，逐个写入就可以了。
建议你先了解清楚程序，内存，磁盘，文件这些基本的概念。
⑶ 怎样将建立好的哈夫曼树保存在文件中
哈夫曼编码是哈夫曼树的一个应用。哈夫曼编码应用广泛，如JPEG中就应用了哈夫曼编码。
首先介绍什么是哈夫曼树。哈夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）。树的带权路径长度记为 WPL=(W1*L1+W2*L2+W3*L3+...+Wn*Ln)，N个权值Wi(i=1,2,...n)构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为Li(i=1,2,...n)。可以证明哈夫曼树的WPL是最小的。
哈夫曼在上世纪五十年代初就提出这种编码时，根据字符出现的概率来构造平均长度最短的编码。它是一种变长的编码。在编码中，若各码字长度严格按照码字所对应符号出现概率的大小的逆序排列，则编码的平均长度是最小的。（注：码字即为符号经哈夫曼编码后得到的编码，其长度是因符号出现的概率而不同，所以说哈夫曼编码是变长的编码。）
一、对给定的n个权值{W1,W2,W3,...,Wi,...,Wn}构成n棵二叉树的初始集合F={T1,T2,T3,...,Ti,...,Tn}，其中每棵二叉树Ti中只有一个权值为Wi的根结点，它的左右子树均为空。（为方便在计算机上实现算法，一般还要求以Ti的权值Wi的升序排列。）
二、在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树，新二叉树的根结点的权值为其左右子树的根结点的权值之和。
三、从F中删除这两棵树，并把这棵新的二叉树同样以升序排列加入到集合F中。
四、重复二和三两步，直到集合F中只有一棵二叉树为止。
用C语言实现上述算法，可用静态的二叉树或动态的二叉树。若用动态的二叉树可用以下数据结构： struct tree{
float weight; /*权值*/union{char leaf; /*叶结点信息字符*/
struct tree *left; /*树的左结点*/};struct tree *right; /*树的右结点*/};struct forest{ /*F集合，以链表形式表示*/
struct tree *ti; /* F中的树*/
struct forest *next; /* 下一个结点*/};例：若字母A，B，Z，C出现的概率为：0.75,0.54,0.28,0.43；则相应的权值为：75，54，28，43。
构造好哈夫曼树后，就可根据哈夫曼树进行编码。例如：上面的字符根据其出现的概率作为权值构造一棵哈夫曼树后，经哈夫曼编码得到的对应的码值。只要使用同一棵哈夫曼树，就可把编码还原成原来那组字符。显然哈夫曼编码是前缀编码，即任一个字符的编码都不是另一个字符的编码的前缀，否则，编码就不能进行翻译。例如：a,b,c,d的编码为：0，10，101，11，对于编码串：1010就可翻译为bb 或ca，因为b的编码是c的编码的前缀。刚才进行哈夫曼编码的规则是从根结点到叶结点（包含原信息）的路径，向左孩子前进编码为0，向右孩子前进编码为 1，当然你也可以反过来规定。
这种编码方法是静态的哈夫曼编码，它对需要编码的数据进行两遍扫描：第一遍统计原数据中各字符出现的频率，利用得到的频率值创建哈夫曼树，并必须把树的信息保存起来，即把字符 0-255(2^8=256)的频率值以2-4BYTES的长度顺序存储起来，（用4Bytes的长度存储频率值，频率值的表示范围为 0--2^32-1，这已足够表示大文件中字符出现的频率了）以便解压时创建同样的哈夫曼树进行解压；第二遍则根据第一遍扫描得到的哈夫曼树进行编码，并把编码后得到的码字存储起来。静态哈夫曼编码方法有一些缺点：一、对于过短的文件进行编码的意义不大，因为光以4BYTES的长度存储哈夫曼树的信息就需1024Bytes的存储空间；二、进行哈夫曼编码，存储编码信息时，若用与通讯网络，就会引起较大的延时；三、对较大的文件进行编码时，频繁的磁盘读写访问会降低数据编码的速度。
因此，后来有人提出了一种动态的哈夫曼编码方法。动态哈夫曼编码使用一棵动态变化的哈夫曼树，对第t+1个字符的编码是根据原始数据中前t个字符得到的哈夫曼树来进行的，编码和解码使用相同的初始哈夫曼树，每处理完一个字符，编码和解码使用相同的方法修改哈夫曼树，所以没有必要为解码而保存哈夫曼树的信息。编码和解码一个字符所需的时间与该字符的编码长度成正比，所以动态哈夫曼编码可实时进行。动态哈夫曼编码比静态哈夫曼编码复杂的多，有兴趣的读者可参考有关数据结构与算法的书籍。
前面提到的JPEG中用到了哈夫曼编码，并不是说JPEG就只用哈夫曼编码就可以了，而是一幅图片经过多个步骤后得到它的一列数值，对这些数值进行哈夫曼编码，以便存储或传输。哈夫曼编码方法比较易懂，大家可以根据它的编码方法，自己编写哈夫曼编码和解码的程序。
⑷ 以二叉链表为存储结构,写出求二叉树高度和宽度的算法
树的高度：对非空二叉树，其深度等于左子树的最大深度加1。
Int Depth(BinTree *T){int dep1,dep2;
if(T==Null) return(0);
else{dep1=Depth(T->lchild);
dep2=Depth(T->rchild);
if(dep1>dep2) return(dep1+1);
else return(dep2+1);}
树的宽度：按层遍历二叉树，采用一个队列q，让根结点入队列，最后出队列，若有左右子树，则左右子树根结点入队列，如此反复，直到队列为空。
int Width(BinTree *T){intfront=-1,rear=-1;
/*队列初始化*／int flag=0,count=0,p;
/* pint CountNode (BTNode *t)
//节点总数{int num;if (t == NULL)num = 0;
elsenum = 1 + CountNode (t->lch) + CountNode (t->rch);
return (num);}void CountLeaf (BTNode *t)
//叶子节点总数{if (t != NULL){if (t->lch == NULL && t->rch == NULL)count ++;
// 全局变量CountLeaf (t->lch);CountLeaf (t->rch);}}。
(4)二叉树存储磁盘扩展阅读
方法：
求二叉树的高度的算法基于对二叉树的三种遍历，可以用后序遍历的算法加上记录现在的高度和已知的最高的叶子的高度，当找到一个比已知高度还要高的叶子，刷新最高高度。
最后遍历下来就是树的高度，至于后序遍历的算法，是一本数据结构或者算法的书中都有介绍和参考代码
⑸ 计算机三级的内容是什么
计算机三级考试大纲全集
一、计算机等级考试三级数据库技术考试大纲
基本要求
1.掌握计算机系统和计算机软件的基本概念、计算机网络的基本知识和应用知识、信息安全的基本概念。
2.掌握数据结构与算法的基本知识并能熟练的应用。
3.掌握并能熟练运用操作系统的基本知识。
4.掌握数据库的基本概念，深入理解关系数据模型、关系数据理论和关系数据库系统，掌握关系数据语言。
5.掌握数据库设计方法，具有数据库设计能力。了解数据库技术发展。
6.掌握计算机操作，并具有C语言编程，开发数据库应用（含上机调试）的能力。
考试内容
一、基础知识
1.计算机系统的组成和应用领域。
2.计算机软件的基础知识。
3.计算机网络的基础知识和应用知识。
4.信息安全的基本概念。
二、数据结构与算法
1.数据结构、算法的基本概念。
2.线性表的定义、存储和运算。
3.树形结构的定义、存储和运算。
4.排序的基本概念和排序方法。
5.检索的基本概念和检索算法。
三、操作系统
1.操作系统的基本概念、主要功能和分类。
2.进程、线程、进程间的通信的基本概念。
3.存储管理、文件管理、设备管理的主要技术。
4.典型操作系统的应用。
四、数据库系统的基本原理
1.数据库的基本概念，数据库系统的组成。
2.数据模型概念和主要的数据模型。
3.关系数据模型的基本概念，关系操作和关系代数。
4.结构化查询语言sql。
5.事务管理、并发控制、故障恢复的基本概念。
五、数据库设计和数据库应用
1.关系数据库的规范化理论。
2.数据库设计的目标、内容和方法。
3.数据库应用开发工具。
4.数据库技术发展。
六、上机操作
1.掌握计算机基本操作。
2.掌握C语言程序设计基本技术、编程和调试。
3.掌握与考试内容相关的知识的上机应用。
考试方式
一、笔试：120分钟
二、上机考试：60分钟
二、等级考试（三级信息管理技术）考试大纲
基本要求
⒈具有计算机及其应用的基础知识。
⒉熟悉计算机操作系统、软件工程和数据库的原理及其应用。
⒊具有计算机体系结构、系统组成和性能评价的基础及应用知识。
⒋具有计算机网络和通信的基础知识。
⒌具有计算机应用项目开发的分析、设计和组织实施的基本能力。
⒍具有计算机应用系统安全和保密性知识。
考试内容
一、计算机系统组成及工作原理
⒈计算机系统组成：
⑴计算机的发展。
⑵计算机的分类及应用。
⑶计算机硬件结构。
⑷主要部件功能。
⑸计算机软件的功能与分类。
⑹系统软件与应用软件。
⒉计算机工作原理：
⑴计算机中数的表示。
⑵运算器。
⑶控制器。
⑷存储器。
⑸输入与输出系统。
⒊计算机的主要性能：
⑴计算机系统性能指标。
⑵处理机指标。
⑶存储容量能力。
⑷I/O总线能力。
⑸系统通信能力。
⑹联机事务处理能力。
⑺软件支持。
二、数据结构与算法
⒈基本概念：
⑴数据结构的基本概念。
⑵算法的描述与分析。
⒉线性表：
⑴线性表的逻辑结构。
⑵线性表的顺序存储结构。
⑶线性表的链式存储结构。
⒊数组：
⑴数组的定义与运算。
⑵数组的顺序存储结构。
⑶矩阵的压缩存储。
⒋栈与队列：
⑴栈的定义和运算。
⑵栈的存储结构。
⑶队列的定义和运算。
⑷链队列与循环队列。
⒌串：
⑴串及其操作。
⑵串的存储结构。
⒍树和二叉树：
⑴树的定义。
⑵二叉树的定义及性质。
⑶二叉树与树的转换。
⑷二叉树的存储。
⑸遍历二叉树与线索二叉树。
⒎图：
⑴图及其存储结构。
⑵图的遍历。
⑶图的连通性。
⑷有向无环图。
⑸最短路径。
⑹拓扑排序。
⒏查找：
⑴线性表查找。
⑵树形结构与查找。
⑶散列查找。
⒐排序：
⑴插入排序。
⑵交换排序。
⑶选择排序。
⑷归并排序。
⑸基数排序。
10.组织：
⑴顺序文件。
⑵索引文件。
⑶散列文件。
三、离散数学
⒈数理逻辑：
⑴命题及其符号化。
⑵命题公式及其分类。
⑶命题逻辑等值演算。
⑷范式。
⑸命题逻辑推理理论。
⑹谓词与量词。
⑺谓词公式与解释。
⑻谓词公式的分类。
⑼谓词逻辑等值演算与前束范式。
(10)谓词逻辑推理理论。
⒉集合论：
⑴集合及其表示。
⑵集合的运算。
⑶有序对与笛卡尔积。
⑷关系及其表示法。
⑸关系的运算。
⑹关系的性质。
⑺关系的闭包。
⑻复合关系与逆关系。
⑼等价关系与偏序关系。
(10)函数及其性质。
(11)反函数与复合函数。
⒊代数系统：
⑴代数运算及其性质。
⑵同态与同构。
⑶半群与群。
⑷子群与陪集。
⑸正规子群与商群。
⑹循环群与置换群。
⑺环与域。
⑻格与布尔代数。
⒋图论：
⑴无向图与有向图。
⑵路、回路与图的连通性。
⑶图的矩阵表示。
⑷最短路径与关键路径。
⑸二部图。
⑹欧拉图与哈密尔顿图。
⑺平面图。
⑻树与生成树。
⑼根树及其应用。
四、操作系统
⒈操作系统的基本概念：
⑴操作系统的功能。
⑵操作系统的基本类型。
⑶操作系统的组成。
⑷操作系统的接口。
⒉进程管理：
⑴进程、线程与进程管理。
⑵进程控制。
⑶进程调度。
⑷进程通信。
⑸死锁。
⒊作业管理：
⑴作业与作业管理。
⑵作业状态及其转换。
⑶作业调度。
⑷作业控制。
⒋存储管理：
⑴存储与存储管理。
⑵虚拟存储原理。
⑶页式存储。
⑷段式存储。
⑸段页式存储。
⑹局部性原理与工作集概念。
⒌文件管理：
⑴文件与文件管理。
⑵文件的分类。
⑶文件结构与存取方式。
⑷文件目录结构。
⑸文件存储管理。
⑹文件存取控制。
⑺文件的使用。
⒍设备管理：
⑴设备与设备分类。
⑵输入输出控制方式。
⑶中断技术。
⑷通道技术。
(5)缓冲技术.
⑹设备分配技术与SPOOLING系统。
⑺磁盘调度。
⑻设备管理。
⒎一种典型操作系统（DOS/Unix/Windows）的使用：
⑴DOS的特点与使用。
⑵UNIX的特点与使用。
⑶Windows的特点与使用。
三|计算机等级考试（三级PC技术）考试大纲
基本要求
1.具有计算机及其应用的基础知识。
2.熟悉80X86微处理器的结构、原理及其宏汇编语言程序设计。
3.掌握个人计算机的工作原理及逻辑组成和物理结构。
4.掌握Windows操作系统的主要功能、原理、配置及其维护管理。
5.熟悉个人计算机常用的外部设备的性能、原理及结构。
考试内容
一、计算机应用的基础知识
1.计算机技术的发展，计算机信息处理的特点，计算机分类，PC机的组成与性能评测。
2.数值信息在计算机内的表示：整数的表示和运算，实数（浮点数）的表示和运算。
3.文字信息与文本在计算机内的表示：西文字符编码字符集（Unicode）。
4.多媒体技术基础：数字声音的类型，波形声音与合成声音，图像、图形的特点与区别，图像、图形和视频信息在计算机内的表示
5.计算机网络的基础知识：计算机网络的功能、分类和组成。数据通信的基本原理，网络体系结构与TCP/IP协议，因特网与IP地址，计算机局域网初步。
二、微处理器与汇编语言程序设计
1.微处理器的一般结构：寄存器组，寄存器管理，总线时序，工作模式以及类型提供配置。
2.Pentium微处理器的功能与结构：内部结构及工作原理，寄存器组，工作模式及存储器管理，中断管理，总线时序。
3.80X86系列微处理器指令系统：指令格式与编码，寻址方式，指令系统。
4.80X86宏汇编语言的数据、表达式和伪指令语句。
5.80X86宏汇编语言的程序设计：顺序、分支及循环程序设计，子程序设计，ROBBIOS中断调用和DOS提供功能调用。
三、PC机组成原理与接口技术
1.PC机的逻辑组成与物理结构：主板与芯片组，超级I/O芯片，主板BIOS等。
2.系统总线的功能与工作原理，ISA总线和PCI局部总线。
3.主存储器的组成与工作原理：ROM和RAM，内存条与主存储器工作原理，Cache存储器。
4.输入输出控制：I/O寻址方式与I/O端口地址，程序控制I/O方式，中断控制I/O方式。DMAI/O控制方式。
5.外设接口：串行接口，并行接口，SCSI接口和IEEE－1394。
四、Windows操作系统的功能与原理
1.操作系统的功能，类型和Windows98体系结构，Windows API与DLL的基本概念。
2.Windows的处理机管理：Windows虚拟机，Windows虚拟机管理程序，Windows的进程调度技术。
3.Windows的存储管理：Windows的内存结构与管理，Windows的虚拟内寻。
4.Windows的文件管理：Windows的文件系统结构，磁盘的存储结构，FAT16与FAT32。
5.Windows的设备管理：虚拟设备驱动程序，通用驱动程序与小型驱动程序，即插即用与配置管理，电源管理，打印子系统等。
6.Windows的网络通信功能：Windows的网络组件，远程网络通信，分布式组件对象模型DCOM，Windows中的Internet组件。
7.Windows的多媒体功能：Windows对多媒体文件与设备的支持，Windows的多媒体组件，Windows的媒体播放器。
8.Windows的配置、管理与维护：安装与启动，注册表，系统配置与管理，系统性能监视和优化，故障诊断。
9.PC机的安全与病毒防范：计算机安全的一般概念，PC机病毒及其防范。
五、PC机的常用外围设备
1.输入设备：键盘、鼠标器、笔输入设备、扫描仪、数码相机，声音输入设备及MIDI输入设备。
2.输出设备：CRT显示其、液晶显示器与显示控制卡，针式打印机、激光印字机与喷墨打印机；绘图仪；MIDI音乐合成、3D环绕声生成与音箱；视频输出设备。
3.外存储器：软盘存储器；硬盘存储器的组成、原理与性能指标，活动硬盘，磁盘阵列；磁带存储器；光盘存储器的原理与分类，CD-ROM、CD-R、CD-RW、DVD光盘存储器。
4.PC机连网设备：Modem，ISDN与PC机的接入，ADSL接入，有线电视网与Cable Modem，局域网组网设备（以太网卡与集线器），无线接入技术。
六、上机操作
1.掌握计算机基本操作。
2.熟练掌握80X86宏汇编语言程序设计的基本技术、编程和调试。
3.掌握与考试内容相关的上机应用。
考试方式
一、笔试：120分钟
二、上机考试：60分钟
⑹ 计算机国四都考什么
俺知道国三的
``
国四的你上网络一搜```
大纲上什么没有呢````
记得是2008版的````
⑺ 如何将数据从磁盘读出并还原成一棵二叉树
题目的意思就是给你中序和先序的序列，让你构造出一个二叉树。构造时用递归的方法（楼主对递归不熟的话很难看懂理解的）
主要思想用递归 对照先序序列，在中序序列中确定根
中序数组in[l1...r1 ]
先序数组pre[ l2...r2]
l1 l2 r1 r2 为数组的下标范围
算法代码如下：
BTNode *CreateBT(char pre[],char in [],int l1,int l2,int r1,int r2)
{
BTNode *s;
int i;
if(l1<r1)return null;
s=(BTNode*)malloc(sizeof(BTNode));
s->lchild=s->rchild=null;
for(i=l2;i<=r2;i++)
if(in[i]==pre[l1])
break;
s->data=in[i];
s->lchild=CreateBT(pre,in,l1+1,l1+i-l2,l2,i-1);
s->rchild=CreateBT(pre,in,l1+i-l2+1,r1,i+1,r2);
return s;
}
⑻ 数据结构按逻辑结构可分为两大类,它们分别是( ) 和( )
从数据的逻辑结构分两大类：线性结构和非线性结构，数据的存储方法有四种：顺序存储方法、链接存储方法、索引存储方法和散列存储方法。
树的存储可能是基于物理上的顺序存储方式，可以理解为一个格子一个格子连续地放，设想有7个节点的二叉树，第一个格子放根节点，第二个格子放左子树根节点；并且根据引用知道左叶子在后续的哪个格子里；第三个格子放右子树根节点，依此类推。此外，树的存储也可能是基于物理上的链式存储方式。
⑼ 如何将该链表中的数据以文件形式保存在磁盘上
楼上的思路是正解，你要是喜欢，我还可以教你一点旁门左道的东西。
其实也简单，就是自定义malloc函数，使得链表在分配空间时在一个限定区段内（比如0000~FFFF）进行分配，即你已经知道了链表可能存在的最大空间，然后保存时，直接用指针：
fwrite()把整个区段写进去，然后再记录根地址即可；
调用时，先把整个区段读进去，然后把根地址读出来作为根，这样整个链表一共用两个指令就完成读写操作了。
不要觉得有多无赖可笑，现代操作系统：WINXP / VISTA / WIN7 / LINUX / OS X等等，其快速“休眠”功能完全就是上面的解法，就是把内存和寄存器状态一并写入磁盘，这个方法非常快，而且不会出错，但是能把教你数据结构的老师气得吐血。
有人说这样产生的文件会很大，大怕什么，压缩一下不就行了？反正里面实际上放置的是一个稀疏矩阵，压缩后的结果可能比楼上产生的文件更小。
⑽ B+树作为Mysql索引结构的优点
面试时候经常会被问到mysql的索引结构，B+树相较二叉树，红黑树的优势等问题，接下来就分析下这些问题。
首先，让我们先看一张图：
从图中可以看到，我们为 user 表（用户信息表）建立了一个二叉查找树的索引。
图中的圆为二叉查找树的节点，节点中存储了键（key）和数据（data）。键对应 user 表中的 id，数据对应 user 表中的行数据。
二叉查找树的特点就是任何节点的左子节点的键值都小于当前节点的键值，右子节点的键值都大于当前节点的键值。顶端的节点我们称为根节点，没有子节点的节点我们称之为叶节点。
如果我们需要查找 id=12 的用户信息，利用我们创建的二叉查找树索引，查找流程如下：
利用二叉查找树我们只需要 3 次即可找到匹配的数据。如果在表中一条条的查找的话，我们需要 6 次才能找到。
上面我们讲解了利用二叉查找树可以快速的找到数据。但是，如果上面的二叉查找树是这样的构造：
这个时候可以看到我们的二叉查找树变成了一个链表。如果我们需要查找 id=17 的用户信息，我们需要查找 7 次，也就相当于全表扫描了。 导致这个现象的原因其实是二叉查找树变得不平衡了，也就是高度太高了，从而导致查找效率的不稳定。为了解决这个问题，我们需要保证二叉查找树一直保持平衡，就需要用到平衡二叉树了。 平衡二叉树又称 AVL 树，在满足二叉查找树特性的基础上，要求每个节点的左右子树的高度差不能超过 1。
下面是平衡二叉树和非平衡二叉树的对比：
由平衡二叉树的构造我们可以发现第一张图中的二叉树其实就是一棵平衡二叉树。
平衡二叉树保证了树的构造是平衡的，当我们插入或删除数据导致不满足平衡二叉树不平衡时，平衡二叉树会进行调整树上的节点来保持平衡。具体的调整方式这里就不介绍了。平衡二叉树相比于二叉查找树来说，查找效率更稳定，总体的查找速度也更快。
因为内存的易失性。一般情况下，我们都会选择将 user 表中的数据和索引存储在磁盘这种外围设备中。但是和内存相比，从磁盘中读取数据的速度会慢上百倍千倍甚至万倍，所以，我们应当尽量减少从磁盘中读取数据的次数。另外，从磁盘中读取数据时，都是按照磁盘块来读取的，并不是一条一条的读。如果我们能把尽量多的数据放进磁盘块中，那一次磁盘读取操作就会读取更多数据，那我们查找数据的时间也会大幅度降低。如果我们用树这种数据结构作为索引的数据结构，那我们每查找一次数据就需要从磁盘中读取一个节点，也就是我们说的一个磁盘块。我们都知道平衡二叉树可是每个节点只存储一个键值和数据的。那说明什么？说明每个磁盘块仅仅存储一个键值和数据！那如果我们要存储海量的数据呢？
可以想象到二叉树的节点将会非常多，高度也会极其高，我们查找数据时也会进行很多次磁盘 IO，我们查找数据的效率将会极低！
为了解决平衡二叉树的这个弊端，我们应该寻找一种单个节点可以存储多个键值和数据的平衡树。也就是我们接下来要说的 B 树。
B 树（Balance Tree）即为平衡树的意思，下图即是一棵 B 树：
图中的 p 节点为指向子节点的指针，二叉查找树和平衡二叉树其实也有，因为图的美观性，被省略了。
图中的每个节点称为页，页就是我们上面说的磁盘块，在 MySQL 中数据读取的基本单位都是页，所以我们这里叫做页更符合 MySQL 中索引的底层数据结构。
从上图可以看出，B 树相对于平衡二叉树，每个节点存储了更多的键值（key）和数据（data），并且每个节点拥有更多的子节点，子节点的个数一般称为阶，上述图中的 B 树为 3 阶 B 树，高度也会很低。
基于这个特性，B 树查找数据读取磁盘的次数将会很少，数据的查找效率也会比平衡二叉树高很多。
假如我们要查找 id=28 的用户信息，那么我们在上图 B 树中查找的流程如下：
B+ 树是对 B 树的进一步优化。让我们先来看下 B+ 树的结构图：
根据上图我们来看下 B+ 树和 B 树有什么不同：
通过上图可以看到，在 InnoDB 中，我们通过数据页之间通过双向链表连接以及叶子节点中数据之间通过单向链表连接的方式可以找到表中所有的数据。
MyISAM 中的 B+ 树索引实现与 InnoDB 中的略有不同。在 MyISAM 中，B+ 树索引的叶子节点并不存储数据，而是存储数据的文件地址。
摘自： http://www.liuzk.com/410.html