一、索引顺序访问方法

* 当字典足够小时,可以整个驻留在内存中时,AVL树和红黑树都能够保证良好的时间性能。
对于那些必须存储在磁盘上的大型字典(外部字典或文件),需要度数更高的搜索树来改善字典操作的性能。在研究这样的搜索树之前,先看一下外部字典的索引顺序访问方法
(ISAM)。这种方法对顺序和随机访问都具有良好的时间性能
块的概念

* 在ISAM方法中,可用的磁盘空间被划分为很多块
* 块是在磁盘空间中用来存储数据的最小单位
* 块一般具有和磁道一样的长度,而且可以在一次搜索和延迟中完成输入或输出
* 字典元素以升序存储在块中。而且这些块按照一种顺序来组织,使得从一块到另一块的延时最短
顺序访问时

* 在顺序访问时,块按序输入,每一个块中的元素按升序搜索
* 如果每个块包含m个元素,则搜索每个元素所需要的磁盘访问次数为1/m
随机访问时(ISAM索引技术)

* 要支持随机访问,就要维持一个索引。索引包含每个块的最大关键字。这样一来,索引中的关键字数量与块的数量相同
,并且每个块都能存储很多元素(即m值通常较大),因此索引足以整个驻留在内存中
* 为了随机访问关键字为k的元素,首先要查找索引表,确定该元素所属的块,然后把相应的快从磁盘中取出进行内部搜索,以确定该元素
* 结果,一次磁盘访问就足以完成一次随机访问 
ISAM在大字典中的应用

* 这种技术可以扩充到更大的字典,这种字典存储在若干个磁盘。这时的元素按升序被分配到不同的磁盘中,在一个磁盘中的元素又按升序被分配到不同的块中
* 每个磁盘都有一个块索引,它保存着在该磁盘中每个块的最大关键字。另外,还有一个磁盘索引,它保存着每个磁盘的最大关键字。磁盘索引一般驻留在内存中
* 为了随机访问一个元素:
* 首先要搜索驻留在内存中的磁盘索引,以确定该元素所属的磁盘
* 然后从该磁盘中取出块索引进行搜索,以确定该元素所属的块
* 最后从磁盘中取出块进行内部搜索,以确定该元素
* 这样一来,一次随机访问需要两次磁盘访问(一次是取出块索引,另一次是取出块)
* ISAM方法本质上是一种数组描述方法,因此,当执行插入和删除时,会面临很大问题。为了部分地缓解问题的压力,可以在每个块中预留一些空间:
* 使得在插入少量元素时,不需要在块与块之间移动元素
* 类似的,在执行删除操作之后,可以把空置的空间保留下来,不必为了节省空间而在块与块之间移动元素
* 使用ISAM方法可以解决这些难题,但是顺序访问的代价提高了
。以任意顺序存储的元素,每一个关键字的索引都要检查,所有元素都通过这个索引来访问。对存储在磁盘上的数据,B-树是一种适合于索引方法的数据结构
二、m叉搜索树

* m叉搜索树可以是一棵空树。如果非空,那么必须满足下面的特征:
* ①在相应的扩充搜索树中(即用外部节点替换空指针之后所得到的的搜索树),每个内部节点最多可以有m个孩子以及1~m-1个元素(外部节点不含元素和孩子)
* ②每一个含有p个元素的节点都有p+1个孩子
* ③对任意一个含有p个元素的节点:
* 设K1,K2,......,Kp分别是这些元素的关键字,这些元素顺序排序,即K1<K2<......<Kp
* 设C0,C1,......,Cp是该节点的p+1个孩子
* 在以C0为根的子树中元素的关键字都小于K1
* 在以Ci为根的子树中,Ki<元素的关键字<K(i+1)。其中1<=i<p
* 在以Cp为根的子树中元素的关键字大于Kp
* 在定义m叉搜索树时,把外部节点包含进来是有用的,不过在实际的代码中,不需要专门描述外部节点,用空指针代替就可以了
* 下图是一棵七叉搜索树,其中黑色代表黑色节点,其他的都是内部节点。例如根节点有两个元素和三个孩子

m叉搜索树的搜索

* 方法:从根节点开始,与节点中的关键字比较,如果比节点中的关键字都大或小,就到相应的子树中进行查找。直到找到或者找不到为止
* 例如查找关键字31:
* 从根节点开始找,31位于10和80之间,于是到根节点的第2个孩子中进行查找
* 从第2孩子查找时,以该孩子为根,发现31位于30与40之间,于是到这个根的第3个孩子中进行查找
* 来到第3个孩子之后,发现比32还小,于是到以该节点为根的第1个孩子中去找,发现为空,于是31不存在
m叉搜索树的插入

* 方法:
从根节点开始插入,如果某节点还有空余空间并且比该空间的所有子节点都大,那么就在该节点的相应位置插入;如果比某个孩子节点中的元素要小,那么就向下移动...以此类推
* 例如插入关键字31:
* 插入根节点,发现不能插入10和80之间,因为比有的子节点的元素要小
* 那么就移动来到第2个子孩子处,但是又不能插入在30和40之间,因为比子孩子节点中的元素值要小
* 那么就再次来到子孩子节点中,发现可以在32的左边插入,于是在插入在32的左边
* 例如插入关键字65:
* 从根节点开始,发现不能插入10和80之间,因为比有的子节点的元素要小
* 那么就移动来到第2个子孩子处,发现可以插入在60和70之间,那么就插入成功
m叉搜索树的删除

* 方法:
* 如果没有孩子节点,那么直接删除
* 如果有孩子(左孩子/右孩子):可以使用左孩子中的最大元素或右孩子中的最小元素来代替删除的这个节点(如果孩子节点元素存在的话)
* 例如删除关键字20:
* 发现该元素没有子孩子,那么可以直接删除。这时节点变为[30、40、50、60、70]
* 例如删除关键字84:
* 发现该元素没有子孩子,也可以直接删除。这时节点变为[82、86、88]
* 例如删除关键字5:
* 节点中之后1个元素,那么删除只有节点就变为空了
* 但是其左孩子为非空,那么可以使用左孩子中的最大元素(4)来替代删除后的这个节点
* 例如删除关键字10:
* 这个元素有两个子孩子
* 那么可以使用左孩子中的最大元素(5)来代替
* 也可以使用右孩子中的最小元素(20)来代替
* 但是如果孩子节点移动上来之后也需要递归考虑子孩子删除的操作
m叉搜索树的高

* 一棵高度为h的m叉搜索树(不含外部节点)最好有h个元素(每层一个节点,每个节点包含一个元素),最多有个元素
* 上限是这样计算的:从1到h-1层,每个节点都含有m个孩子,第h层的节点没有孩子,这时的节点个数为,而每个节点最多有m-1元素,因此元素个数为
* 因为在高度为h的m叉搜索树中,元素个数在h到之间,所以一棵n元素的m叉搜索树的高度在到n之间
* 例如,一棵高度为5的200叉搜索树能够容纳的元素做多是,最少是5。同样,一棵含有个元素的200叉搜索树,其高度在5到之间
* 当搜索树存储在磁盘上时,搜索、插入、删除的时间取决于磁盘的访问次数(假设每一个节点的大小不大于一个磁盘块)。当h是树的高度时,这个次数为O(h),因此,
要减少磁盘访问次数,就要确保树的高度接近于,为此就要利用m叉搜索树
三、m阶B-树

* m阶B-树是一棵m叉搜索树。如果B-树非空,那么有如下的规则:
* ①根节点至少有2个孩子
* ②除根节点以外,所有内部节点至少有m/2个孩子
* ③所有外部节点在同一层
满二叉树

* 在二阶B-树中,每个内部节点都不会有2个以上的孩子,而每个内部节点又至少有2个孩子,因此二阶B-树的所有内部节点都恰好有2个孩子
* 又因为所有外部节点都在同一层上,所以二阶B-树是满二叉树
* 因此,对某个整数h,仅当元素个数为时,这样的树才存在
* 下面一棵七阶B-树:
* 根节点有3个孩子:满足规则①
* 内部节点至少有3,满足规则②
* 所有外部节点在同一层,满足规则③

* 二阶B-树(man二叉树)
*  
 

 

 

技术
©2019-2020 Toolsou All rights reserved,
Vue常用特性(一)百度、阿里、腾讯内部岗位级别和薪资结构,附带求职建议!【虚拟机踩坑记】此主机支持 Intel VT-x,但 Intel VT-x 处于禁用状态。苹果与日产对话暂停,Apple Car进展如何?一文揭秘阿里、腾讯、百度的薪资职级Java基础(冒泡排序)TP6验证器的使用示例及正确验证数据一年半JAVA工作经验的总结谷歌称居家办公影响工作效率!2021 年将回归线下办公这些歌,程序员千万万万万别听!