会计学9.1文件(wénjiàn)概述9.1文件(wénjiàn)概述9.1文件(wénjiàn)概述9.1文件(wénjiàn)概述9.1文件(wénjiàn)概述9.1文件(wénjiàn)概述9.2顺序(shùnxù)文件顺序(shùnxù)文件在存储介质中可以有两种不同的实现结构：连续结构和链结构。9.2顺序(shùnxù)文件9.2顺序(shùnxù)文件9.2顺序(shùnxù)文件9.2顺序(shùnxù)文件9.2顺序(shùnxù)文件9.2顺序(shùnxù)文件9.2顺序(shùnxù)文件9.3索引(suǒyǐn)文件9.3索引(suǒyǐn)文件9.3索引(suǒyǐn)文件B树是一种平衡的多路查找树，它在数据处理中有着巨大的作用，已经成为数据处理中主要(zhǔyào)的文件组织形式。它以占用存储空间少，查找效率高的优势在数据库系统的索引技术中占据了重要的地位。定义：一棵m阶的B树，或者为空树，或为满足下列特性的m叉树。（1）对树中子树的要求：每个结点至多有m棵子树。若根结点不是叶子结点，则至少有两棵子树。除根结点之外的所有非终端结点至少有m/2棵子树。（2）对树中关键字个数的要求：所有的非终端结点中包含(bāohán)以下信息(n，A0，K1，A1，K2，…，Kn，An)。其中，n为关键字个数，m/21≤n≤m1；Ki（i=1,2,…,n）为关键字，且Ki<Ki+1；Ai为指向子树根结点的指针（i=0,1,…,n），且指针Ai－1所指子树中所有结点的关键字值均小于Ki（i=1,2,…,n），An所指子树中所有结点的关键字值均大于Kn。（3）对叶子结点的要求：所有的叶子结点都出现在同一层次上，并且不带信息（可以看做是外部结点或查找失败的结点，实际上这些结点不存在，指向这些结点的指针为空）。例一棵5阶的B树9.4B-树与B+树9.4B-树与B+树9.4B-树与B+树9.4B-树与B+树B+树是应文件系统所需而产生的一种B树的变形树。一棵m阶的B+树和m阶的B树的差异在于：（1）在B树中，每个结点含n个关键字，n+1棵子树；在B+树中，每个结点含n个关键字，n棵子树。（2）在B树中，每个结点中关键字个数n的取值范围m/21≤n≤m1（除根）结点外。在B+树中，每个结点中关键字个数n的取值范围m/2≤n≤m（除根结点外），1≤n≤m（根结点）。（3）B+树中所有叶子结点包含了全部关键字及指向对应记录的指针，且所有叶子结点按关键字由小到大顺序(shùnxù)依次链接。（4）B+树中所有非叶子结点仅起索引作用，结点中仅含有其子树中的最大（或最小）关键字。9.4B-树与B+树9.4B-树与B+树9.5杂凑(zácòu)（Hash）文件9.5杂凑(zácòu)（Hash）文件9.5杂凑(zácòu)（Hash）文件9.5杂凑(zácòu)（Hash）文件9.5杂凑(zácòu)（Hash）文件散列技术的关键问题：⑵冲突的处理。如何采取合适的处理冲突方法来解决冲突。①Hash函数。若Hash函数选择(xuǎnzé)得当，就可使Hash地址尽可能均匀地分布在Hash地址空间上，从而减少冲突的发生；否则，若Hash函数选择(xuǎnzé)不当，就可能使Hash地址集中于某些区域，从而加大冲突的发生。②处理冲突的方法。选择(xuǎnzé)适当的Hash函数可以减少冲突，但不能避免冲突，因此当冲突发生时，必须有较好的处理冲突的方法。③Hash表的装填因子。9.5杂凑(zácòu)（Hash）文件9.5杂凑(zácòu)（Hash）文件根据关键码在各个位上的分布情况，选取分布比较均匀(jūnyún)的若干位组成散列地址。对关键码平方后，按散列表(lièbiǎo)大小，取中间的若干位作为散列地址（平方后截取）。将关键码从左到右分割成位数相等的几部分，将这几部分叠加求和(qiúhé)，取后几位作为散列地址。由关键码得到的散列地址一旦产生了冲突，就去寻找(xúnzhǎo)下一个空的散列地址，并将记录存入。9.5杂凑(zácòu)（Hash）文件例：有关键字序列为{36，7，40，11，16，81，22，8，14}，Hash表表长为11，Hash(key)=key%11，用线性探测法处理冲突(chōngtū)，建立Hash表例以上例中的关键字建立(jiànlì)Hash表。用二次探测法处理冲突，建立(jiànlì)Hash表9.5杂凑(zácòu)（Hash）文件9.5杂凑(zácòu)（Hash）文件例关键字序列为{36，7，40，11，16，81，22，8，14}，Hash函数为Hash(key)=key%11用链地址(dìzhǐ)法处理冲突，建立Hash表9.5杂