阅读裘宗燕老师的《数据结构与算法:python语言描述》的课件所记笔记

一、数据存储、检索和字典

  • 存储和检索是计算机中最重要最基本的工作
  • 基于关键码的数据存储和检索
    • 关键码指数据项的某种(可能具有唯一性的)特征,可以是数据内容的组成部分,也可以是专门为数据检索建立的标签
    • 支持这种操作的数据结构,通常称为字典、查找表或映射

二、字典

  • 最主要同时也是最频繁的操作是检索
    • 检索效率
    • 检索效率重要性因字典规模不同可能不同
  • 分类:
    • 静态字典:建立后保持不变,只做检索,实现只需考虑检索效率
    • 动态字典:内容经常动态变动。需要考虑插入和删除操作的效率
    • 动态字典的插入和删除操作可能导致字典结构的变化。长期使用需考虑保证结构的稳定及良好的检索效率(性能不应随着反复操作而恶化)
  • 检索效率评价标准:关键码的平均比较次数,称为平均检索长度ASL(Average Search Length),定义:
    $$ASL=\sum_{i=0}^{n-1}p_ic_i$$
    其中n为字典的项数,ci和pi为数据元素i的检索长度和概率。若个检索概论都一样,则pi=1/n,ASL=1/n。可能还需考虑找不到的情况

1.字典和索引

  • 字典是两种功能的统一:
    • 作为数据的存储结构,支持数据的存储
    • 提供支持数据检索的功能,维护关键码到所存数据的联系
  • 索引是字典的附属结构,只提供检索功能
    • 可能提供与基本字典不同的查找方式,例如另一套关键码
    • 基于关键码的索引,实现的是关键码到数据存储位置的映射
    • 字典可以没有另外的索引,只有自身提供的检索方式;也可以附有一个或多个索引,如《新华字典》
  • 实现字典与实现索引
    • 实现字典时,关键码关联于实际数据,数据保存在字典
    • 实现索引时,关键码关联于数据在字典里保存的位置

2.字典元素:关联

class Assoc(object):
    def __init__(self, key, value):
        self.key = key
        self.value = value

    def __lt__(self, other):
        return self.key < other.key

    def __le__(self, other):
        return self.key < other.key or self.key == other.key

    def __str__(self):
        return "Assoc({0},{1})".format(self.key, self.value)

若x的值是关联,x.key取得关键码,x.value取得关联值;定义<和<=用于比较数据。

三、字典实现

  • 实现技术:
    • 线性表,特别是连续表
    • 散列表
    • 基于树形结构

1.线性表表示

  • 由于线性表可以存储信息,因此可以作为实现方式:
    • 关联在线性表里顺序排列,形成关联的序列
    • 检索是在线性表里查找具有特定关键码的数据项,插入和删除操作都是普通的线性表操作
  • 顺序字典可以用list实现
    • 关联可用Assoc对象,也可用二元tuple或list实现
    • 检索就是在表中查找特定的关键码(顺序查找),找到就说明检索成功;若检查完表还未找到,则检索失败
    • 插入新关联用append实现;删除可以在定位后用del实现,或是基于要删除的内容,用remove实现
  • 优点与缺点:
    • 优点:数据结构和算法简单,适用于任何关键码集合
    • 缺点: 平均检索长度大,表长达n较大时检索耗时长,删除的效率也比较低,不太适合频繁变动的字典
    • 在字典的动态变化中,各种操作的效率不变(因为都已经是很低的操作了)

2.有序线性表和二分检索

  • 关键码取自一个有序集,将字典里的项按关键码排列。由于数据项排列有序,因此可以采用二分法实现快速检索
  • 基本过程:
    • 初始考虑范围是整个字典
    • 取考虑范围的中间项进行比较,若相等则检索结束;若小于则考虑范围缩小为中间项左侧的数据,大于则是右侧的数据
    • 若范围里已经没有数据,则检索失败;否则重复上述步骤
a.二分检索程序实现
def bisearch(lst, key):
    low, hight= 0, len(lst)-1
    while low <= hight:
        mid = (low + hight)//2
        if lst[mid].key == key:
            return list[mid].value
        if lst[mid].key < key:
            low = mid + 1
        else:
            hight = mid - 1
b.X实现分析
  • 插入的一个特殊情况是被查关键码存在,可修改关联值或插入新项(允许关键码重复),删除时分删除一项还是所有关键码相同的项
  • 检索过程可用二叉树表示,数据位置标在树结点,通过检索找到某结点的比较次数等于该结点的层数加1

3.X字典操作效率

四、散列表(hash table,哈希表,杂凑表)

  • 当关键码是连续表下标时,检索速度最快,可直接找到元素。关键码可能不是整数,即使是,也可能取值范围很大,不适合直接作为下标。
  • 散列表基本思想:把基于关键码的检索变为基于整数下标的访问
    • 方法:选定一个整数下标范围建立一个连续表;选定一个从关键码集合到该下标范围的适当映射h
    • 存入关键码为key的数据时,将其存入表第h(key)个位置
    • 以key为关键码检索数据时,直接去查第h(key)个位置的元素
  • 上述h称为散列函数,又称哈希函数或杂凑函数,是从可能的关键码到一个整数区间里(下标)的映射。其类型是:
    h:KEY ——> INDEX

1.散列技术:设计和性质

  • 将散列计算应用于存储和检索,就得到了散列表
  • 对于散列表,通常有|KEY|>>|INDEX|
    h把一个大集合的元素映射到一个小集合里,必然会有多个关键码对于同一个位置的情况,此时就说出现冲突(碰撞),也称这些关键码为同义词
    上述可知,对规模固定的散列表,一般表中元素越多,出现冲突的可能性越大,用‘负载因子’作为一种有用的度量
  • 负载因子a是考察散列表性质的一个重要参数。定义:
    a = 散列表中实际元素个数/基本存储区能容纳的元素个数
    负载因子越大,出现冲突可能性也越大。散列表中实际元素越多,说明需要映射的元素越多,出现冲突可能也越大;基本存储区能容纳的元素个数即映射的下标位置个数,增大存储空间(增大可能存储位置)可以减小负载因子。但负载因子小,空闲空间的比例就大。
a.散列表设计实现两大问题
  • 散列函数设计,冲突消除机制。首先考虑散列函数的设计问题
  • 关键码和位置区间是事先确定的,作为散列函数的基础集合(参数域和值域)。选择散列函数需考虑:
    • 尽可能把关键码映射到不同值,尽可能映射到值域中的大部分
    • 关键码的散列值在下标区间里均匀分布,有可能减少冲突
    • 计算比较简单
  • 散列表设计实现两大问题:散列函数设计,冲突消除机制

2.散列函数

  • 基本思想:映射关系越乱越好,越没有规律越好
  • 一些方法依赖于对实际数据集的分析,实际中很难使用
    • 如果事先知道需要存储的数据及其分布,可能设计出一个存储效果最佳的散列函数,甚至可能保证不出现冲突
    • 一些数据结构教科书里介绍了一批散列函数设计
    • 常见情况是需要存储和使用的数据不能再设计字典之前确定,具体使用和分布情况未知,上述分析方法不可用,只能用一些通用方法
a.除余法
  • 关键码是整数。以关键码除以一个不大于散列表长度m的整数p得到的余数(或者余数加1)作为散列地址
    m常取2的某个幂值,此时p可以取小于m的最大素数(如果连续表的下标从1开始,可以用余数加1)
  • 设计散列函数的最基本想法是使得到的结果尽可能没有规律
    • 采用除余法,如果用偶数作为除数,就会出现偶数关键码得到偶数散列值,奇数关键码得到奇数散列值
    • 如果关键码集合的数字位数较多,可以考虑采用较大的除数,然后去掉最低位,排除最低位的规律性。还可以考虑其它去掉规律性的方法
b.基数转换法
  • 针对整数关键码。取一个正整数r,把关键码看作基数为r的数,将其转换为十进制或二进制数。通常r取一个素数。最后用除余法或删除几位数字的方法将其归入所需范围
  • 对于非整数关键码,通常先设计一种方法转换为整数,然后用整数散列的方法。通常最后用除余法把关键码归入所需范围
  • 对于字符串关键码。常见方法是把一个字符看做一个整数(例如用字符的编码),把一个字符串看作以某个整数为基数的“数”
    • 常以29或31为基数,用基数转换法转换为整数
    • 再用整数散列法,把结果归入下标范围

3.冲突的消除

  • 分为:
    • 内消除方法(在基本存储区内解决元素冲突)
    • 外消除方法(在基本存储区外解决元素冲突)
  • 对冲突处理技术的基本要求:
    • 保证存入当前数据项的工作能够完成
    • 保证字典的基本存储性质:在任何时候,从任何以前存入字典而后未删除的关键码出发,都能找到对应的数据项
a.开地址法和探查序列
  • 开地址法(内消除法):
    • 出现冲突时设法在连续表里为要插入的数据项另安排一个位置
    • 需要设计一种系统的且易于计算的位置安排方式(称为探查方式)
  • 常用方法是为散列表定义一个探查位置序列:
    Hi = (h(key) + di) mod m
    其中m为不超过表长的数,di为一个增量序列,设d0 = 0,插入数据项时,如果h(key)空闲就直接存入(相当于使用d0),否则就逐个试探位置Hi,直到找到第一个空位时把数据项存入
  • 增量序列有多种可能取法,例如
    取di = 0,1,2,3,...,称为线性探查;设计另一散列函数h2,令di = i * h2(key),称为双散列探查。使用线性探查容易出现堆积现象,即在处理同义词时又引进非同义词之间冲突。其它探查法也可能出现这种情况,但可能稍好
  • 检索过程与插入类似。为判定“找不到”,还需为“无值”确定一种表示方式。对给定的key:
    • 用散列函数求出对应的散列地址
    • 如果该位置无数据项,检索失败
    • 否则比较数据项的关键码,如果相等则检索成功并结束
    • 否则根据散列表的探查序列找到“下一地址”并回到步骤2
  • 删除,若找到对应项后简单将其删除,将可能影响后面的检索操作:
    • 如果被删除元素位于同一散列值或不同散列值的检索链上,直接删除就会导致检索链的破坏
    • 解决办法:在被删除元素处放一个特殊标记(与空位标记不同)。检索时将其看作有元素存在,继承探查;插入时看作是空位
b.溢出区
  • 外消除冲突的一种方法是在基本存储区之外,另外设置一个公共溢出区,把所有关键码冲突的数据项都保存在这个溢出表里
  • 如果散列表里的数据项很多,溢出区就可能变得很大;随着数据项的增加,插入和检索的工作量都会趋于线性
  • 采用了公共溢出区的散列表,散列表的负载因子可能超过1
c.拉链法
  • 数据项不存放在散列表里,而是另外存储。散列表里保存对数据项的引用,由此可以有很多可能的设计。最简单的技术是“拉链法”
  • 基本思想:数据项存在散列表的基本连续表之外,每个关键码建立一个链接表,所有关键字为同义词的数据项存在同一链表里

4.散列表的实现

  • 实际中,拉链法还可以推广
    • “同义词表”也可以采用顺序表或散列表,还可以采用其他结构
    • 有时把存放同义词的表称为“桶”,称这种结构为“桶散列”
    • 可用于存储大型字典,或者用于组织大量文件
  • 无论采用哪种消除方法,随着元素增加,负载因子增大,出现冲突的可能性会明显增大。在开地址法中,最终导致存储区溢出;在溢出区方法里是溢出区越来越大,检索效率趋于线性。在拉链法中表现为链的平均长度增加

5.扩大存储

  • 负载因子达到一定程度扩大基本存储表,明显的时间与空间交换
    • 采用内消除的一般情况
      经验说明负载因子a<=0.7~0.75时平均检索长度接近常数
    • 采用桶散列,负载因子就是桶的平均大小
      可以容忍任意大的负载因子,但随着其增大,检索时间趋于线性

五、字典和集合

  • 任何字典实现方法都可用于实现集合,因为集合也代表一种关联,元素是否属于集合。

1.集合的实现

a.X基于排序表实现
b.X基于散列表实现
c.特殊实现技术:位向量实现
  • 一个元素是否属于一个集合,是一种二值判断。基于这一认识,提出专门的集合实现技术:位向量表示
  • 如果所需要的集合对象有一个公共超集U,即需要实现的集合都是U的子集,就可以采用位向量技术实现这些集合,方法是:
    • 假定U包含n个元素,给每个元素一个编号作为该元素的“下标”
    • 对任何要考虑的集合S,用一个n位的二进制序列(位向量)Vs表示S。对于元素e属于U,如果e属于S,令Vs里对应于e(下标编号)的那个位取值1,否则取值0
  • 例如:假设U是{a, b, c, d, e, f},其子集
    S1 = {a, b, c}:111000,S2 = {b, e, f}:010011

2.python字典和集合

  • python内置字典(dict)和集合(set和frozenset),都是基于散列表实现的数据结构,采用内消除技术
    • 建立空字典或小字典,初始创建的存储区可容纳8个元素
    • 负载因子超过2/3时更换更大存储快。字典不太大时按当时元素中实际元素的4倍分配新快。超过50000时按实际元素的两倍分配新块
  • python中dict的关键码,set和frozenset的元素都只能是不变对象。为保证散列表的完整性

3.python的散列

  • python标准函数中有hash函数用于计算参数的散列值,hash
    • 是函数,对一个对象调用或返回一个整数或抛出异常表示无定义
    • 对数值类型有定义,保证当a==b时两个数的hash值相同
    • 对内置不变组合类型有定义,包括str,tuple,frozenset
    • 对无定义的对象调用,例如包含可变成分的序列,hash将抛出TypeError:unhashable type...
  • 调用时hash到参数所属的类里找名为hash的方法
    • hash有定义的内置类型都有自己的hash方法
    • 自定义类里也可以定义这个方法

4.对字典的进一步考虑

  • 前面两种结构:
    • 基于线性表的结构简单,易于实现。但总存在低效操作,不适合大型字典
    • 散列表操作效率高,对关键码类型无特殊要求,应用广泛。但没有确定性的效率保证,不适合效率要求严格的环境
  • 两种结构需要大块连续存储,动态变化不方便,也难于用于实现巨大的字典。要支持方便的动态变化,就应该考虑链接结构。分析上述情况很容易想到树形结构
    • 可以用链接方式实现,容易处理动态插入/删除元素操作
    • 树中平均路径的长度可以达到结点个数的对数,有可能实现高效操作

六、基于树实现字典

  • 用于实现字典的树形结构考虑因素:
    • 支持大型字典的需要
    • 支持高效的结构调整
    • 有可能较好地利用计算机系统的存储结构
  • 特别注意二叉树的如下特点:
    • 树结构‘良好’,最长路径长度与结点个数成对数关系
    • 树结构‘畸形’,则成线性关系
  • 采用(链接实现)二叉树作为字典的存储结构
    • 可能得到较高的检索效率
    • 采用链接的实现方式,数据项的插入、删除操作比较灵活方便
  • 实现优势:
    • 通常平均高度远小于树中结点个数
    • 沿着树中路径进行检索,效率高

1.二叉排序树

  • 是一种存储数据的二叉树:
    • 可用于保存关键码有序的数据
    • 树中数据的存储和使用都利用了数据的序
    • 可作为一种基于二叉树结构实现字典的方法
  • 定义:二叉排序树或者为空,或者具有如下性质的二叉树:
    • 根结点保存着一个数据项(包括关键码)
    • 若左子树不为空,则其所有结点保存的值均小于根结点所保存的值
    • 若右子树不为空,则其所有结点保存的值均大于根结点所保存的值
    • 左右子树也满足二叉排序树
  • 二叉排序树是一种递归结构
    • 对其做中序遍历,得到按关键码排序的“上升”序列
    • 如果存在重复关键码,则它们的不同数据项的前后顺序不确定
    • 同时关键码相同的数据必定位于中序遍历后的相邻位置

2.二叉树排序树:实现

a.X检索实现
def bt_search(btree, key):
    bt = btree
    while bt is not None:
        entry = bt.data
        if key < entry.key:
            bt = bt.left
        elif key > entry.key:
            bt = bt.right
        else:
            return entry.value
    return None
b.X基于二叉排序的字典实现
from BiTree1 import BiTNode, print_BiTNodes
from SStack import *
from Assoc import Assoc

class DictBiTree(object):
    def __init__(self):
        self._root = None

    def is_empty(self):
        return self._root == None

    def inorder(self):
        t, s = self._root, SStack()
        while t is not None or not s.is_empty():
            while t is not None:
                s.push(t); t = t.left
            t = s.pop();yield(t.data);t = t.right
    #与bt_search()类似        
    def search(self, key):
        ...
c.X插入操作
def insert(self, key, value):
    t = self._root
    if t is None:
        self._root = BiTNode(Assoc(key, value))
        return
    while True:
        entry = t.data
        if key < entry.key:
            if t.left is None:
                t.left = BiTNode(Assoc(key, value))
                return
            t = t.left
        elif key > entry.key:
            if t.right is None:
                t.right = BiTNode(Assoc(key, value))
                return
            t = t.right
        else:
            entry.value = value
            return
d.删除操作
  • 检索到要删除的结点,删除的同时还需维护二叉排序树的完整性,即树形结构完整,非删除结点仍在,整棵树依然是二叉排序树
实现分析
  • 三种情况,假设被删除结点为q:
    • 被删除结点q是叶结点
      • 直接删除即可
    • 被删除结点q只有左子树或只有右子树
      • 删除结点q后将其左子树或右子树的根结点填补q中的空位
    • 被删除结点q左右子树都存在,两种处理方式:
      • 从q的左子树中取出值最大的结点l填补q的空位,分配l的左子树为q中取掉最大值的左子树,右子树为q的右子树
      • 用左子树根结点填补空位,将右子树根结点连接到左子树中值最大的结点
程序实现
def del(self, key)
    p, q= self._root, None
    while p is not None and p.data.key != key:
        q = p
        if key < p.data.key:
            p = p.left
        else: p = p.right
    if p is None: return
    if p.left is None:
        if q is None: self._root = p.right
        elif p == q.left: q.left = p.right
        else: q.right = p.right
        return
    r = p.left
    while r is not None:
        r = r.right
    r.right = p.right
    if q is None: self._root = p.left
    elif p == q.left:q.left = p.left
    else: q.right = p.left
e.X操作性能

3.最佳二叉排序树

  • 平均检索效率最高(平均检索路径最短)的二叉排序树
  • 扩充二叉排序树的对称序列:
    按中序遍历扩充二叉树得到结点标记序列。其中内外结点交叉排列,第i个内部结点位于第i个与第i+1个外部结点之间
  • 扩充二叉排序树表示了一个字典的可能关键码集合:
    • 内部结点代表已有元素的关键码
    • 外部结点代表介于两个相邻内部结点的关键码之间的那些关键码
  • 扩充二叉树,根结点层数为0:
    • 内部结点需比较层数加1次,从根结点开始第一次比较,到检索位置的最后一次比较
    • 外部结点比较次数等于层数,由于是集合,不用进行最后一次当前位置的比较
a.等概率最佳二叉排序树构造
  • 各结点被检索的概率相等时。采用递归构造(左右子树结点均分的方法),设表a里是按关键码排序的一组字典项
    • 令low = 0, high = len(a)-1
    • m = (high + low)/2
    • 把a[m]存入被构造二叉排序树的根结点t,递归地:
      • 将基于a[low:m]构造的二叉排序树作为t的左子树
      • 将基于a[m+1:len(a)]构造的二叉排序树作为t的右子树
      • 切片为空时直接返回NULL,表示空树
X程序实现
b.不等概率最佳二叉排序树构造
  • 一颗最佳二叉排序树的左右子树必定为最佳二叉排序树
  • 构造思想:
    • 给定排序的关键码序列[key0,key1,...,keyn-1]和两个权序列[p0,...,pn-1]与[q0,q1,...,qn]
    • 比较上述序列构成的所有左右子树为最佳二叉排序树的二叉排序树,选出左右最佳二叉排序子树之和最小的,假设这时根结点为i,代价即为该二叉排序树所有结点权值之和W(0,n)加上其左右子树T(0,i)、T(i+1,n),该二叉排序树即为该序列的最佳二叉排序树
    • 重复上述步骤计算最佳二叉排序子树
  • 核心思想:计算排序序列中所有可能的最佳二叉排序子树
X程序实现

4.平衡二叉排序树(AVL树)

  • 最佳二叉排序树的查询效率高。但这种结构需要根据所有元素的情况静态构造,适合静态字典表示,不能很好地支持动态变化
  • 原因:最佳是全局性质,难以在局部把握、检查和调整
  • 支持字典动态操作的树形结构
    • 共性都是放弃最佳性质,设法提供某些接近最佳的性质,换取在动态操作中较易通过局部调整进行维护
  • 基本想法:如果每个结点左右子树的高度差不多,树的结构会比较好,不会出现特别长的路径
  • 定义:平衡二叉排序树或是空树,或是左右子树都是平衡二叉排序,而且左右子树的高度之差的绝对值不超过1。平衡由各结点的情况刻画,用简单平衡因子BF(Balace Factor)描述。BF定义为结点左右子树的高度差,可能取值只有-1,0,1
a.X实现
  • 与前面类似,只是需要增加一个bf属性
b.插入操作
  • 破环平衡发生在离插入结点最近的根结点bf绝对值为1的平衡子树T。
    • 若不存在,即所有结点的bf都为0,则只需更改插入结点的父结点bf值即可
    • 若存在,且插入T中较低的一侧,只需调整相应结点的bf值
    • 其他情况都需调整因插入结点后变成的不平衡子树T'
四种情况程序实现
  • 设a为T'的根节点,b为左右子树根结点
    1.左高插入左子树左边,把左子树根结点b的右边作为T'的根结点a的左边,把新的根结点a'作为b的右边
    def LL(a, b):
    a.left = b.right
    b.right = a
    a.bf = b.bf = 0
    return b

    2.右高插入右子树右边,把右子树根结点b的左边作为T'的根结点a的右边,把新的根结点a'作为b的左边

    def RR(a, b):
    a.right = b.left
    b.left = a
    a.bf = b.bf = 0
    return b

    3.左高插入左子树的右边,把左子树根结点b的右边替换为b的右子树根结点c的左边,把根结点a的左边替换为c的右边,把新的b'作为c的左子树,新的a'作为c的右子树

    def LR(a, b):
    c = b.right
    a.left, b.right = c.right, c.left
    c. left, c.right = b, a
    if c.bf == 0:
        a.bf=b.bf=0
    elif c.bf == 1:
        a.bf = -1; b.bf = 0
    else:
        a.bf = 0; b.bf = 1
    c.bf = 0
    return c

    4.右高插入右子树的左边,把右子树根结点b的左边替换为b的左子树根结点c的右边,把根结点a的右边替换为c的左边,把新的a'作为c的左子树,新的b'作为c的右子树

    def RL(a, b):
    c = b.left
    a.right, b.left = c.left, c.right
    c.left, c.right = a, b
    if c.bf == 0:
        a.bf = b.bf = 0
    elif c.bf == 1:
        a.bf = 0; b.bf = -1
    else:
        a.bf = 1; b.bf = 0
    c.bf = 0
    return c
c.XAVL树插入算法
d.X删除操作

七.其它支持字典的树形结构

  • 基于多分支排序树,共性是保持到叶结点的所有路径长度相同,并保证每个分支结点至少有两个或更多分支,这样n个结点的树里的路径长度不会超过O(log n)
  • 多分支排序树的分支结点保存一些关键码信息,作为检索时的导向
    • 如果一个分支结点有k棵子树,就用k-1个关键码区分各子树保存的值。检索时通过与这些关键码比较就能觉得进入哪棵子树
  • 实现多分支排序树的一个问题是每个结点的大小可能变动
    • 为便于管理,通常采用统一大小结点,这决定了最大分支树m
    • 为保证空间利用率(和良好树结构),规定结点的最小分支数大于或等于2
    • 允许结点的分支数在2~m范围内变化
  • 维持树高度的技术:
    • 加入数据时,若目标结点数据项数将要超出允许范围,则或在兄弟结点间调整数据项(同时修改父结点关键码),或分割结点
    • 删除数据时,若目标结点数据项数将要低于允许范围,则或在其兄弟结点之间调整,或者合并结点
a.B树
  • 一棵m阶B树或空,或有下面特征:
    • 分支结点至多m-1个排序存放的关键码。根结点至少一个关键码,其它结点至少⎣(m-1)/2⎦ 个关键码
    • 如果分支结点有j个关键码,则包含j+1棵子树,结点信息为序列($p_0,k_0,p_1,k_1,...,k_j-1,p_j$),其中k为关键码,p为子结点引用,$k_i$大于子树$p_i$里所有的关键码,小于$p_i+1$里的所有关键码
b.B+树
  • 一棵m阶B+树或为空,或满足下列条件:
    • 每个分支结点至多有m棵子树,除根外的分支结点至少有⎡m/2⎤棵子树,如果根结点不是叶结点则至少有两棵子树
    • 结点里排序存储关键码,叶结点保存数据项的关键码及其存储位置,分支结点里的一个关键码关联着一个棵子树,这个关键码等于其子树的根结点里的最大关键码
    • 叶结点可以看作基本索引块,分支结点看作索引的索引
最后由 oucb 编辑于2017年05月11日 14:11