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