2-3-4树
定义
234表示一个节点可能还有子节点的个数,有以下三种情况:
如果使用L表示子节点的个数,D表示数据项的个数,那么L=D+1,非叶子节点个数总比它数据项含有的数据项多1.
树的组织
节点中的数据项按照关键字升序排列。
搜索2-3-4树
从根开始查找,除非查找的关键字就是根,否则会选择关键字所在的范围,直到找到位置。
插入
查找时没有满节点时很简单,将数据项插入即可,当节点已满时,涉及到节点的移动。
如果对应的节点都已满,会发生数据项的分裂,关于几种分裂,此处不再赘述。
树的效率
查找时间复杂度为O(log N).
外部存储
RAM
随机存取存储器(英文:random access memory,RAM)又称作“随机存储器”,是与CPU直接交换数据的内部存储器,也叫主存。它可以随时读写,而且速度很快,通常作为操作系统或其他正在运行中的程序的临时数据存储媒介。
ROM
ROM所存数据,一般是装入整机前事先写好的,整机工作过程中只能读出,而不像随机存储器那样能快速地、方便地加以改写。ROM所存数据稳定,断电后所存数据也不会改变;其结构较简单,读出较方便,因而常用于存储各种固定程序和数据。除少数品种的只读存储器(如字符发生器)可以通用之外,不同用户所需只读存储器的内容不同。为便于使 用和大批 量 生产 ,进一步发展了可编程只读存储器(PROM)、可擦可编程序只读存储器(EPROM)和电可擦可编程只读存储器。
第10章 2-3-4树和外部存储,布布扣,bubuko.com
原文:http://blog.csdn.net/michael10001/article/details/26853713