readme.txt

B+树的演示程序

	B+树演示程序的说明

如有界面说明、功能说明、程序说明、文件说明、类说明等图片，请先看图。

================================================

此程序可分为三个部分：数据部分、控制部分、绘图部分。

一、数据部分：B+树的数据及查找、插入、删除等。

MyNode	结点类，是内部结点与叶子结点的基类。
      它含有long k[N]及void* p[N+1]，未使用new long[N]及new void*[N+1]，因在delete时常发生错误，而进调试确信并没有越界访问，错误原因不明，在此处仅采用了预先留出足够空间的方案。

MyBranch	内部结点类。:public MyNode
      无新增的成员变量，成员函数主要是重载了MyNode类的虚函数，实现查找 Search()，插入 Insert()，分裂结点 SplitNode()，删除 Delete()，从左（右）得到一键-指针对 GetKeyFromLeft() GetKeyFromRight()，与右相邻结点合并 UniteRight() 的功能。

MyLeaf	叶子结点类。:public MyNode
       新增一个变量MyLeaf* m_next用于指向右邻叶子结点。它同样重载了在MyBranch()中提到的MyNode中的虚函数，具体实现叶子结点中相应功能的操作。

MyBPlusTree	B+树类，实现B+树的查找、插入、删除算法。
       成员变量主要包括B+树根结点指针m_root及当前操作结点指针m_current，还有是B+树的统计量树高m_levels，结点总数m_nodes，记录总数m_keys等。
       成员函数为查找、插入、删除的具体功能实现。
       (1)查找：Search()以m_root为参量调用 SearchKey()，SearchKey()中查找pnode的了结点中key应属的指针范围，如其子结点仍为内部结点，则以该子结点为参数再次调用SearchKey()，直到叶子结点，在叶子结点中判断*(long*)p[i] == key否成立，即知key是否在B+树中。
       (2)插入：首先Search()得知是否重复插入，Insert()中以参数level调用InsertKey()，InsertKey()中把key插入树的第level层，当结点满时分裂结点SplitNode()，后以参数level+1调用InsertKey()，直到不分裂插入，或分裂至根结点，进行new MyBranch并更新结点数据及B+树统计量，完成插入过程。
       (3)删除：首先Search()得知B+树中是否含有该key，Delete()中以level参数调用 DeleteKey() ， DeleteKey() 中在树的第level层上查找到key所在范围的键-指针对，并删除，在m_n == M时调用JudgeNbrNode()判断删除方案，有可移动键-指针对时，调用pnode->GetKeyFromLeft()或GetKeyFromRight()实现从左或右相邻结点移动键-指针对，如无可移动键-指针对，调用pnode->UniteRight()实现结点的合并，并将更新的key及指针以参数level+1调用DeleteKey()递归到无合并发生，或删除到根结点进行delete和更新数据的操作，最后调用Update()在level到树高m_levels间更新键值k[]。
       (4)创建与删除：用Create(int n)创建n型的空B+树，DeleteTree()调用DelTree()递归逐级删除所有结点。

二、控制部分：数据与视图的交互。

MyControl作为MVC的控制部分，传递数据与视图的交互信息，并在相中实现框架响应的消息的具体实现，同时在数据部分完成操作后，负责通知显示部分进行B+树的列表、绘图显示。比如B+树的编辑窗口的“创建B+树”按钮的相应实际仅是向MyControl类传送了创建要求。

三、显示部分：包括编辑窗口、CTreeCtrl列表显示、及GDI的B+树绘制。

CMainFrame及MyControlDlg是用户交互的主要窗口，它们向MyControl传递消息由MyControl进行具体功能的组织实现。

CTreeCtrl	树型列表的显示，递归函数逐结点用InsertItem()完成。

CChindView::OnPaint() 中用MyDrawBPlusTree::DrawTree()进行B+树的绘制。

MyDrawNode	根据parameters.h中define的预置参数绘制单个结点，绘制文本，绘制箭头。

MyDrawBPlusTree	绘制B+树。
      数据由MyBPlusTree型指针m_tree获取数据，其主要是组织绘制递归，确定position的作用。
      (1)确定所需绘制的结点，由m_drawKey0及m_drawLevel决定所需点，在GetFirstNodeKey0中根据绘制结点在m_firstDrawLevel层的对应结点左侧相邻结点情况决定m_firstDrawKey0，即可确定第一绘制点。
      (2)递归的绘制过程，在DrawSubNode()中对pnode的子结点进行绘制，并记录返回的position信息，完成子结点绘制后由子结点的position信息确定该结点的position信息。
      (3)对于所需绘制点的不同状态在DrawNode()进行各种不同的绘制。具体为：
	switch(m_iType)
	{
	case 1:	// search			绘制高亮结点
	case 10:	// insert long in leaf		高亮绘制key及箭头指向叶子结点
	case 11:	// insert in node		高亮绘制node及箭头指向内部结点
	case 12:	// insert root		新增根结点
	case 13:	// insert splide		分裂结点
	case 15:	// insert complete		插入过程完成，高亮绘制key
	case 20:	// delete key		删除key，已取消，原因见问题4
	case 21:	// delete root		删除根结点，已取消，原因见问题4
	default:	// draw normal		正常绘制结点
	}

===============================================

已知的问题：

1.在结点数据中因使用new操作赋予的空间常发生delete时出错的现象（原因未察明，仅在删除操作的合并结点时有时发生，经调试又无越界访问，不明所以），在程序实现时使用的指定最大N值，指定数组元素个数的方式；

2.在单视图中加入多窗体采用了下载到的一个容器类，但其使用必须要求主窗体含工具栏控件，并且在关闭该容器后调用ShowWindow(SW_SHOW)并不能重新使窗口显示出来，即在使用时如关闭了某一容器，只能重启程序才可令容器出现；

3.在CTreeCtrl中查找后用SelectItem()没有实现高亮选择所查找的结点，同时没有添加消息响应函数，对单击树型列表作任何的处理；

4.在B+树的绘制演示时，仅完成了插入的演示，在尝试删除演示时出现很多问题，初步判断认为是在绘制时调用了MyBPlusTree::SearchKey()与在B+树的删除时亦用此函数造成冲突而产生的；

5.最终发布时debug及release版本在有些机器让并不是按本机调试的状态运行，已知的情况是在某些时候不进行绘制，如发生该情况请用另一版本测试。

================================================

由于时间及水平有限，程序中有大量不足之处，望老师予以批评指正。