现在位置: 首页 / 数据结构 / 正文

查找-数据结构

查找-数据结构

基本概念

查找：在数据集合中寻找满足某种条件的数据元素的过程称为查找

查找表（查找结构）：用于查找的数据集合称为查找表，它由同一类型的数据元素（或记录）组成

关键字：数据元素中唯一标识该元素的某个数据项的值，使用基于关键字的查找，查找结果应该是唯一的

比如：

学号 姓名 语文 数学 英语
202001 小菜 99 98 97
202002 小莫 87 87 87
202003 小果 88 07 68
202004 小冻 87 27 66
202005 小奶 76 67 54

查找表：学生成绩信息（线性结构、可顺序可链式存储）

数据元素（记录）：每个学生的信息

关键字：学号

查找表的常见操作

对于静态查找表，查找符合条件的数据元素，仅关注查找速度即可

对于动态查找表，不仅需要查找符合条件的数据元素，还要查找、删除某个数据元素，除了查找速度，也要关注插入、删除操作是否方便实现

查找算法的评价指标

查找长度：在查找运算中，需要对比关键字的次数被称为查找长度

平均查找长度（ASL，Average Search Length）：所有查找过程中进行关键字对比次数的平均值，ASL的数量级反映了查找算法的时间复杂度

查找算法的评价指标

评价⼀个查找算法的效率时，通常考虑查找成功/查找失败两种情况的 ASL

顺序查找

顺序查找，⼜叫“线性查找”，通常⽤于线性表。算法思想：从头到尾扫描元素（反之也可）

typedef struct {  //查找表的顺序结构
    ElemType *elem;  //动态数组基址
    int TableLen;  //表的长度
}SSTable;

//顺序查找
int Search_Seq(SSTable ST,ElemType key){
    int i;
    for(i=0;i<ST.TableLen && ST.elem[i]!=key;++i);
    //查找成功，则返回元素下标；查找失败则返回-1（三元条件运算符）
    return i==ST.TableLen? -1:i;
}

或者为了提高代码的效率，可以在数组内设置一个哨兵，倒序扫描。优点是无需判断越界，效率更⾼

    typedef struct {  //查找表的顺序结构
    ElemType *elem;  //动态数组基址
    int TableLen;  //表的长度
}SSTable;

//顺序查找
int Search_Seq(SSTable ST,ElemType key){
    ST.elem[0]=key;
    int i;
    for(i=0;i<ST.TableLen && ST.elem[i]!=key;++i);
    //查找成功，则返回元素下标；查找失败则返回-1（三元条件运算符）
    return i==ST.TableLen? -1:i;
}

$$ ASL成功=\frac{1+2+3+...+n}{n}=\frac{n+1}{2} $$

$$ ASL失败=n+1 $$

顺序查找的优化（对有序表）

顺序查找的优化

一个成功结点的查找长度=自身所在的层数，一个失败结点的查找长度=其父节点所在层数。默认情况下，各种失败情况和成功情况都等概率发生

在被查概率不相等的情况下，可以将被查概率大的元素放在靠前的位置

折半查找

折半查找，⼜称“⼆分查找”，仅适⽤于有序的顺序表。它的核心思想是通过不断地将搜索区间减半来缩小目标值可能存在的范围，直至找到目标值或确定目标值不存在于数组中。每次比较都能排除掉一半的元素，因此其时间复杂度为 O(log~2~n)，其中 n 是数组的长度。

#include "function.h"

typedef struct {  //查找表的顺序结构
    ElemType *elem;  //动态数组基址
    int TableLen;  //表的长度
}SSTable;

//折半查找
int Binary_Search(SSTable ST,ElemType key){
    int low=0,high=ST.TableLen-1,mid;
    while(low<=high){
        mid=(low+high)/2;  //取中间位置
        if(ST.elem[mid]==key)
        {
            return mid;  //查找成功则返回所在位置
        } else if(ST.elem[mid]>key)
        {
            high=mid-1;  //从前半部分继续查找
        } else
        {
            low=mid+1; //从后半部分继续查找
        }
        return -1;  //查找失败，返回-1
    }
}

如果当前low和high之间有奇数个元素，则 mid 分隔后，左右两部分元素个数相等。如果当前low和high之间有偶数个元素，则mid分隔后，左半部分比右半部分少一个元素。折半查找的判定树中，若 mid=向下取整{(low+high)/2}，则对于任何⼀个结点，必有：右⼦树结点数-左⼦树结点数=0或1

折半查找的判定树⼀定是平衡⼆叉树，在折半查找的判定树中，只有最下⾯⼀层是不满的，因此元素个数为n时树高h=log~2~（n+1）

判定树结点关键字：左<中<右，满⾜⼆叉排序树的定义。失败结点：n+1个（等于成功结点的空链域数量）

分块查找

分块查找，也称为索引顺序查找，是一种介于顺序查找和二分查找之间的查找算法。它的基本思想是将查找表分成若干个块（子表），并对每个块建立一个索引，这些索引包含了每个块中的最大关键字和块在表中的起始位置。索引表是有序的，可以通过二分查找或顺序查找来确定待查记录所在的块。一旦确定了块，就在该块内进行顺序查找

分块查找的算法思想

若索引表中不包含目标关键字，则折半查找索引表最终停在low>high，要在low所指分块中查找，这是因为最终low左边⼀定⼩于⽬标关键字，high右边⼀定⼤于⽬标关键字。⽽分块存储的索引表中保存的是各个分块的最⼤关键字。

查找效率分析（ASL）

假设，长度为n的查找表被均匀地分成b块，每块s个元素。设索引查找和块内查找的平均查找长度分别为L~1~，L~2~，则分块查找的平均查找长度为ASL=L~1~+L~2~。用顺序查找索引表，则 $$ L1=\frac{(1+2+...+b)}{b}=\frac{b+1}{2} $$

$$ L2=\frac{(1+2+...+s)}{s}=\frac{s+1}{2} $$

$$ ASL=L1+L2=\frac{b+1}{2}+\frac{s+1}{2}=\frac{s^2+2s+n}{2s} $$

$$ 当s=\sqrt{n},ASL最小为\sqrt{n}+1 $$

如果是折半查找索引表，则

$$ L1=log_2(b+1) $$

$$ L2=\frac{(1+2+...+s)}{s}=\frac{s+1}{2} $$

$$ ASL=L1+L2=log_2(b+1)+\frac{s+1}{2} $$

二叉排序树（BST）

二叉排序树，又称二叉查找树（BST，Binary Search Tree）。二叉排序树可用于元素的有序组织、搜索。一棵二叉树或空二叉树，或者是具有如下性质的二叉树：

1.左子树上所有结点的关键字均小于根节点的关键字

2.右子树上所有结点的关键字均大于根节点的关键字

3.左子树和右子树又各是一棵二叉排序树

这种性质，使得二叉排序树在进行中序遍历时，可以得到一个递增的有序序列

二叉排序树的查找

性质：左子树结点值 < 根结点值 < 右子树结点值

若树非空，目标值与根节点的值比较；若相等，则查找成功。若小于根节点，则在左子树上查找，否则在右子树上查找。查找成功返回结点指针；查找失败返回NULL。

//二叉树排序树结点
typedef struct BSTNode{
    int key;
    struct BSTNode *lchild,*rchild;
}BSTNode,*BSTree;

//在二叉排序树中查找值为key的结点
BSTNode *BST_Search(BSTree T,int key){
    while (T!=NULL&&key!=T->key)  //若树空或等于根结点值，则结束循环
    {
        if(key<T->key)  //小于，则在左子树上寻找
        {
            T=T->lchild;
        } 
        else  //大于，则在右子树上寻找
        {
          T=T->rchild;  
        }
    }
    return T;
}

//在二叉排序树中查找值为key的结点（递归实现）
BSTNode *BSTSearch(BSTree T,int key){
    if(T==NULL)
    {
        return NULL; //查找失败
    }
    if(key=T->key)
    {
        return T;  //查找成功
    } else if(key <T->key){
        return BSTSearch(T->lchild,key);  //在左子树中查找
    } else
    {
        return BSTSearch(T->rchild,key);  //在右子树中查找
    }

}
二叉排序树的插入

若原二叉排序树为空，则直接插入结点；否则，若关键字K小于根结点值，则插入左子树，若关键字K大于根结点值，则插入到右子树

//在二叉排序树插入关键字K的新结点（递归实现）
int BST_Insert(BSTree &T,int k){
    if(T==NULL){  //原树为空，新插入的结点为根节点
        T=(BSTree) malloc(sizeof(BSTNode));
        T->key=k;
        T->lchild=T->rchild=NULL;
        return 1;  //返回1，插入成功
    }
    else if(k==T->key)  //树中存在相同关键字的结点，插入失败
    {
        return 0;
    } else if(k<T->key)  //插入到T的左子树
    {
        return BST_Insert(T->lchild,k);
    } else  //插入到T的右子树
    {
        return BST_Insert(T->rchild,k);
    }
}
二叉排序树的构造

通过上面的方法，可以构造一棵二叉排序树

//按照str[]中的关键字序列建立二叉排序树
void Creat_BST(BSTree &T,int str[],int n){
    T=NULL;  //初始时T为空树
    int i=0;
    while (i<n)  //依次将每个关键字插入到二叉排序树中
    {
        BST_Insert(T,str[i]);
        i++;
    }
}

不同的关键字序列可能得到相同的二叉排序树，也要可能得到不同的二叉排序树

二叉排序树的删除

先搜索找到目标结点

1.若被删除的结点z是叶结点，则直接删除，不会破坏二叉排序树的性质

2.若结点z只有一棵左子树和右子树，则让z的子树成为z父节点的子树，替代z的位置

3.若结点z有左、右两棵子树，则令z的直接后继（或直接前驱）替代z，然后从二叉排序树中删除这个直接后继（或直接前驱），这样就转化为了第一或第二种情况

二叉排序树删除

查找效率分析

查找效率分析

平衡二叉树

平衡二叉树（Balanced Binary Tree），简称平衡树（AVL树）：树上的任一结点的左子树和右子树的高度之差不超过1

结点的平衡因子：左子树高-右子树高。平衡二叉树结点的平衡因子的值只能是-1、0和1。只要有任一结点的平衡因子绝对值大于1，就不是平衡二叉树

typedef struct AVLNode{
    int key;  //数据域
    int balance;  //平衡因子
    struct AVLNode *lchild,*rchild;
}AVLNode,*AVLTree;
平衡二叉树的插入

在二叉排序树中插入新结点后，查找路径上的所有结点都有可能受到影响（不平衡），解决方法是从插入点往回找到第一个不平衡结点，调整以该结点为根的子树。每次调整的对象都是"最小不平衡子树"。在插入操作中，只要将最小不平衡子树调整平衡，其他祖先结点都会恢复平衡

调整最小不平衡子树有四种情况，分别对应四种不同的调整方式

LL：在A的左孩子的左子树中插入导致不平衡

LL

RR：在A的右孩子的右子树中插入导致不平衡

RR

LR：在A的左孩子的右子树中插入导致不平衡

LR平衡旋转（先左后右双旋转）。由于在A的左孩子的右子树上插入新结点，A的平衡因子由1增至2，导致A为根的子树失去平衡，需要进行两次旋转操作，先左旋转再右旋转。先将A的左孩子B的右子树的根节点C向左上旋转提升到B结点的位置，然后再把该C结点向右上旋转提升到A结点的位置。

LR

RL：在A的右孩子的左子树中插入导致不平衡

RL平衡旋转（先右后左双旋转）由于在A的右孩子的左子树上插入新结点，A的平衡因子由-1减至-2，导致以A为根的子树失去平衡，需要进行两次旋转操作。先右旋再左旋转。现将A结点的右孩子的左子树的根结点C向右上旋转提升到B结点的位置，然后再把C结点向左上旋转提升到A结点的位置

RL

查找效率分析

若树高为h，则最坏情况下，查找一个关键字最多需要对比h次，即查找操作的时间复杂度不可能超过O(h)

平衡二叉树：树上任一结点的左子树和右子树的高度之差不超过1。假设以n~h~表示深度为h的平衡树中含有的最少结点数，则有n~0~=0，n~1~=1，n~2~=2，并且有n~h~=n~h-1~+n~h-2~+1。可以证明含义n个结点的平衡二叉树的最大深度为O(log~2~n)，平衡二叉树的平均查找长度为O(log~2~n)

平衡二叉树的删除

平衡二叉树的插入操作：

1、若插入新结点后，要保持二叉排序树的特性不变（左<中<右）

2、若插入新结点导致不平衡，则需要调整平衡

平衡二叉树的删除操作：

1、删除结点后，要保持二叉排序树的特性不变（左<中<右）

2、若删除结点导致不平衡，则需要调整平衡

平衡二叉树删除操作的具体步骤“

1、删除结点

2、向上寻找最小不平衡子树，若无法找到，则证明平衡

3、找最小不平衡子树下，最高的儿子结点和孙子结点

4、根据孙子结点的位置，进行平衡调整（LL\RR\LR\RL）

5、如果不平衡向上传导，则重复步骤2

AVL树删除

红黑树

红黑树是一种自平衡的二叉查找树，它不仅包含了二叉查找树的所有性质，还引入了额外的颜色属性（红色或黑色），以及一系列用于维持树平衡的性质。在红黑树中，每个节点都有一个颜色属性，根节点是黑色的，所有叶子节点（空节点）也是黑色的。此外，红黑树还禁止有两个连续的红色节点，并且从任一节点到其每个叶子节点的所有路径上，包含相同数目的黑色节点

红黑树的性质确保了树的平衡，从而提供了高效的查找、插入和删除操作。这些性质包括：

1、每个节点是红色或黑色。

2、根节点是黑色的。

3、所有叶子节点（外部结点、NULL结点、失败结点）是黑色的。

4、不存在两个相邻的红结点（即红节点的父节点和孩子结点均是黑色的）。

5、对于每个结点，从该结点到任一叶结点的简单路径上，所含黑结点的数目相同。

这些性质共同作用，使得从根到叶子的最长路径不多于最短路径的两倍，从而保证了树的平衡性和操作的效率

红黑树相较于普通二叉查找树的优势主要体现在以下几个方面：

自平衡性：红黑树是一种自平衡的二叉查找树，它通过节点着色（红色或黑色）和一系列的平衡规则来维护树的平衡性。这意味着即使在频繁的插入和删除操作后，红黑树也能保持相对平衡的形态，避免了普通二叉查找树可能出现的最坏情况下的线性时间复杂度。

高效的操作性能：由于红黑树的高度近似于对数级别，它的查找、插入和删除操作的时间复杂度都能保持在O(log~2~n)的水平。这使得红黑树在处理大量数据时仍能保持高效率。

防止退化成链表：普通二叉查找树在某些情况下可能退化成单链表，这时其性能会急剧下降至O(n)。而红黑树通过其自平衡机制，能够有效防止这种退化现象，保证了操作的稳定性。

支持区间查询：红黑树的有序性使得它能够支持高效的区间查询操作，这在数据库索引等应用中非常有用。

广泛的应用场景：红黑树的设计哲学和性能特点使其成为多种数据结构和算法的基础，如C++ STL中的map和set、Java中的TreeMap和TreeSet等，广泛应用于需要高效数据管理的场景。 

struct RBnode{  //红黑树的结点定义
    int key;  //关键字的值
    RBnode* parent;  //父节点指针
    RBnode* lchild;  //左孩子指针
    RBnode* rchild;  //右孩子指针
    int color;  //结点颜色，如0/1代表黑/红，也可以用枚举型enum表示颜色
};

结点的黑高bh：从某结点出发（不含该结点）到达任一空叶结点的路径上黑结点总数

红黑树的插入

红黑树的插入步骤：

1、先查找，确定插入位置（原理同二叉排序树），插入新结点，若新结点是根则染为黑色，新结点非根，染成红色。

2、若插入新结点后依然满足红黑树定义，则插入结束。若插入新结点后不满足红黑树定义，需要调整（看新结点叔叔节点的颜色），使其重新满足红黑树定义。

3、若新结点的叔叔结点是黑色，则染色+旋转，具体要求

  • LL：右单旋，父换爷+染色
  • RR：左单旋，父换爷+染色
  • LR：左、右双旋，儿换爷+染色
  • RL：右、左双旋，儿换爷+染色

4、若新结点的叔叔节点是红色，则染色+变新，具体要求：叔父爷结点染色，爷结点变新结点

红黑树插入

红黑树的删除

红黑树删除操作的时间复杂度是O(log~2~n)

红黑树中删除结点的处理方式和二叉排序树的删除是一样的，但是在删除操作之后，可能破坏红黑树特性，此时需要调整结点颜色、位置，使其再次满足红黑树特性。

  1. 定位要删除的节点：首先在红黑树中找到要删除的节点。
  2. 处理删除节点的特殊情况：如果要删除的节点是红色的，直接删除并更新父节点的指针即可，因为红色节点的删除不会破坏树的平衡性质。如果要删除的节点是黑色的，且只有一个子节点或没有子节点，需要找到其替代节点（通常是直接前驱或后继节点），并用该替代节点替换要删除的节点。
  3. 删除节点后的平衡调整：删除黑色节点后，可能会破坏红黑树的平衡性质。这时需要通过一系列的旋转和重着色操作来恢复平衡。这些操作包括左旋、右旋以及改变节点颜色。调整的具体策略取决于被删除节点的父节点和叔叔节点的颜色，以及它们相对于被删除节点的位置。
  4. 递归调整：在某些情况下，删除节点后的调整可能会导致更高层次的不平衡，需要递归地向上调整直至根节点，或者直到达到平衡状态。
  5. 更新根节点颜色：如果在调整过程中根节点变成红色，需要将其颜色改为黑色，以满足红黑树根节点必须是黑色的性质。
B树

B树（B-Tree）是一种自平衡的多路查找树，它能够保持数据有序，适用于磁盘或其他直接存取的辅助存储设备。B树的特点包括：

  1. 多路性：每个节点可以有多于两个子节点，这有助于减少树的高度，提高查找效率。
  2. 平衡性：所有叶子节点都在同一层，或者树的高度相对较低，确保了操作的高效性。
  3. 关键字分布：节点中的关键字从小到大排列，且每个关键字恰好分割其子节点中的关键字区间。
  4. 内部节点和叶子节点：内部节点包含关键字和子节点指针，叶子节点通常不包含指针，只包含关键字。
  5. 插入和删除操作：当节点满时，会进行分裂；当节点不满时，可能需要合并或调整关键字分配。

B树的设计目标是减少磁盘I/O操作次数，提高数据检索速度，因此它在数据库和文件系统中被广泛应用.

B树相对于二叉查找树（BST）具有以下优势：

  1. 高度平衡：B树是一种多路平衡查找树，所有叶子节点都处于同一层，这有助于减少查找操作的时间复杂度，即使在最坏情况下也能保持对数时间复杂度O(log~2~n)。
  2. 减少磁盘I/O操作：B树的内部节点存储关键字信息，叶子节点包含实际数据或数据的地址，这种结构可以通过最少的I/O操作来定位到数据，减少了磁盘I/O的次数。
  3. 顺序访问性能好：由于B树的叶子节点形成了一个有序链表，因此范围查找非常高效，适合数据库中需要频繁进行范围查询的情况。
  4. 缓存友好：B树的节点通常比较大，在内存中能够容纳更多的关键字和数据，从而提高了缓存命中率，减少了频繁的磁盘访问。
  5. 空间利用率高：B树的每个节点可以存储多个关键字和子节点指针，这使得B树在存储大量数据时具有较高的空间利用率。
  6. 自平衡特性：B树在插入和删除操作后能够自动保持平衡状态，不需要像某些自平衡二叉查找树（如AVL树）那样进行复杂的旋转操作。
  7. 支持高效的数据插入和删除：B树的设计考虑了外部存储的特性，插入和删除操作不会导致树的高度急剧增加，因此维护成本较低。

m叉查找树中，规定除了根节点外，任何结点⾄少有（向上取整[m/2]）个分叉，即⾄少含有（向上取整[m/2]）-1个关键字

m叉查找树中，规定对于任何⼀个结点，其所有⼦树的⾼度都要相同

B树

B树的插入

B树的插入操作是一种动态维护数据平衡的过程，主要包括以下几个步骤：

  1. 定位插入位置：从根节点开始，根据关键字值向下遍历，直至找到叶子节点，这是插入新关键字的位置。
  2. 插入关键字：将新关键字插入到叶子节点中，并保持关键字有序。如果叶子节点未满（即关键字数量少于最大值），直接插入并结束操作。
  3. 处理节点分裂：如果插入后叶子节点的关键字数量超过了最大值，需要进行分裂操作。分裂通常涉及到将节点中间的关键字上移到父节点，并将节点分成两个新节点，每个新节点包含原节点的一部分关键字和子节点。
  4. 调整父节点：如果分裂导致父节点的关键字数量超过最大值，需要继续向上分裂，直到达到根节点或父节点的关键字数量满足条件。
  5. 更新根节点：如果分裂发生在根节点，根节点会分裂成两个新的根节点，并相应地调整树的结构。

核心要求：

1、对于m阶B树，除根节点外，结点关键字个数(向上取整[m/2]-1)<=n<=m-1

2、子树0<关键字1<子树1<关键字2<子树2<...

3、新元素一定是插入到最底层"终端节点"，用"查找"来确定插入位置

B树的删除

在B树中，当执行删除操作后，需要确定是否需要对删除节点进行合并，以维持B树的平衡性。

1、若被删除关键字在终端结点，则直接删除该关键字（要注意结点关键字个数是否低于下限（向上取值m/2）-1）

2、若被删除关键字在非终端结点，则用该结点的直接前驱或直接后继来替代被删除的关键字（直接前驱：当前关键字左侧指针所指子树中"最右下"的元素，直接后继：当前关键字右侧指针所指子树中"最左下"的元素）。对非终端结点关键字的删除，必然可以转化为对终端结点的删除操作

归根结底是探索终端结点的删除操作：

  1. 节点关键字数量不足：如果删除操作后，节点的关键字数量小于树的最小填充因子（通常是 ⌈m/2⌉ - 1，其中 m 是节点的最大关键字容量），节点将不满足B树的定义。
  2. 兄弟节点的关键字数量不足以借出：即使删除后节点的关键字数量小于最小填充因子，如果该节点的兄弟节点（位于同一父节点下）的关键字数量也不足以借出一个关键字，或者借出关键字后兄弟节点的关键字数量也将小于最小填充因子，则需要进行合并。
  3. 兄弟节点的关键字足以借出：若被删除关键字所在结点删除前的关键字个数低于下限，且与此结点右或左兄弟结点的关键字个数还很充裕，则需要调整该结点右或左兄弟结点及其双亲结点（父子换位法）。当右兄弟很宽裕时，用当前结点的后继、后继的后继来填补空缺，当左兄弟很宽裕时，用当前结点的前驱、前驱的前驱来填补空缺。
  4. 根节点的特殊情况：如果删除操作发生在根节点，并且根节点的子节点数量小于最小填充因子，根节点本身可能会被删除，并且其子节点可能会合并成为新的根节点。
  5. 合并后的节点满足填充因子要求：合并后的新节点的关键字数量应至少达到树的最小填充因子，以确保B树的平衡。

本质：要永远保证 ⼦树0<关键字1<⼦树1<关键字2<⼦树2<….

B+树

B树和B+树是两种常用的自平衡多路查找树数据结构，它们在数据库和文件系统中广泛应用于索引组织。B+树是B树的变体，两者在节点存储方式、叶子节点的结构以及数据检索效率等方面有所不同。

1.节点存储方式

  • B树：每个节点（包括叶子节点和非叶子节点）都存储键值和数据，非叶子节点的关键字用于指示子节点的范围.
  • B+树：只有叶子节点存储键值和数据，非叶子节点仅作为索引，存储键值以指示子节点的范围，叶子节点之间通过指针连接形成有序链表.

叶子节点的结构

  • B树：叶子节点之间没有指针连接，数据分散在各个节点中.
  • B+树：所有叶子节点通过指针连接，形成一个有序链表，便于范围查询和顺序访问.

数据检索效率

  • B树：由于数据分布在各个节点中，范围查询可能需要在多个节点间进行，效率不如B+树.
  • B+树：由于所有数据都在叶子节点，且叶子节点之间有序连接，范围查询和顺序访问更为高效.

B+树通常在数据库系统中更受青睐，因为它提供了更稳定的查询性能和更高效的范围查询能力.

B树和B+树是两种自平衡的多路查找树，广泛用于数据库和文件系统的索引结构。它们在存储数据方面的主要差异体现在数据分布和节点设计上：

  1. 数据分布：
    • 在B树中，每个节点不仅包含索引，还直接包含实际的数据记录。这意味着非叶子节点和叶子节点都可能包含数据。
    • 相比之下，B+树的非叶子节点只包含索引信息，即子节点中关键字的最大值和指向子节点的指针，而所有的数据记录都存储在叶子节点中。这导致B+树的叶子节点形成一个有序的链表，便于进行顺序访问和范围查询。
  2. 节点设计：
    • B树的节点设计较为灵活，允许非叶子节点拥有可变数量的子节点，只要这个数量在一定范围内（通常是−1至m−1）。
    • B+树的节点设计更为严格，每个非叶子节点必须有固定数量的子节点，其关键字个数等于子节点数减一（⌈m/2⌉至m）。此外，B+树的叶节点包含了全部关键字及指向相应记录的指针，并且这些关键字是排序的。

这些差异使得B+树在磁盘I/O操作上更加高效，因为在查询时不需要遍历非叶子节点，而且由于所有数据集中在叶子节点，可以在内存页中获取更多的键，从而加快查找范围的缩小速度.

B+树相较于B树在数据库系统中更受青睐，主要得益于以下几个方面的优势：

  1. 查询效率更稳定：B+树的所有关键字数据都存在叶子节点上，这意味着每次查找的次数都相同，从而保证了查询速度的稳定性。
  2. 更适合区间查询：B+树的叶子节点之间通过指针连接形成链表，这使得区间查询变得更加高效。只需要通过头结点向下找到第一个叶子节点，然后在叶子节点的链表上进行遍历即可完成区间查询。
  3. 减少非叶子节点的存储开销：B+树的非叶子节点只包含键信息，不包含数据，相比B树的非叶子节点既包含键又包含数据，因此B+树的非叶子节点可以存储更多的键，减少了树的高度。
  4. 更适合顺序访问：由于B+树的叶子节点形成了有序链表，支持更高效的范围扫描和顺序访问，这对于范围查询、分页查询等操作更为高效。
  5. 磁盘IO优化：B+树的有序叶子节点形成了顺序存储，减少了磁盘IO的次数，提高了磁盘读取效率。
  6. 简化的范围查询实现：在B+树中，范围查询仅需要遍历叶子节点上的链表，而在B树中可能需要遍历多个层次的节点。

这些优势使得B+树成为数据库系统中常用的索引结构，尤其是在需要支持大量数据和频繁查询时，B+树能够提供更好的性能和存储效率。

B+树的叶子节点之间通过指针相连接的原因主要有以下几点：

  1. 优化范围查询：由于所有的数据记录都存储在叶子节点上，并且叶子节点之间通过指针形成了一个有序链表，这使得B+树在执行范围查询时非常高效。可以直接在叶子节点之间移动，而无需回溯到上层节点。
  2. 提高缓存效率：由于树的高度较低且叶节点位于同一层，结合叶子节点之间的指针连接，可以更有效地利用缓存来存储树的结构和数据，从而提高数据访问速度。
  3. 简化查询操作：所有叶节点具有相同的高度，这有助于简化查询算法的实现，因为查询操作在到达叶节点之前所经过的路径长度是固定的。
  4. 维护数据顺序：叶子节点之间的指针连接确保了数据按照关键字的顺序组织，这对于顺序扫描数据集非常有用，特别是在数据库管理系统中进行全表扫描时。

一棵m阶B+树需满足下列条件：

  1. 每个分支结点最多有m棵子树（孩子结点）
  2. 非叶根节点至少有两棵子树，其他每个分支结点至少有⌈m/2⌉棵子树
  3. 结点的子树个数与关键字个数相等
  4. 所有叶结点包含全部关键字及指向相应记录的指针，叶结点中将关键字按大小顺序排列，并且相邻叶结点按大小顺序相互链接起来（支持顺序查找）
  5. 所有分支节点中仅包含它的各个子结点中关键字的最大值和指向其子结点的指针

综上所述，叶子节点之间的指针连接是为了提高B+树在数据检索方面的性能，尤其是在处理范围查询和顺序访问时提供了便利。

散列表

散列表（哈希表，Hash Table）：是一种数据结构。特点是可以根据元素的关键字计算出它在散列表中的存储地址

散列函数（哈希函数）：Addr=H（key），建立了关键字到存储地址的映射关系

散列表

冲突（碰撞）：在散列表中插入了一个数据元素时，需要根据关键字的值确定其存储地址，若该地址已经存储了其他元素，则称这种情况为冲突（碰撞）

同义词：若不同的关键字通过散列函数映射到同一个存储地址，则称他们为同义词

构造更适合的散列函数，让各个关键字尽可能地映射到不同的存储位置，从而减少冲突

散列函数的构造

核心目标：散列函数要尽可能地减少冲突

设置散列函数需要注意：

  1. 定义域必须涵盖所有可能出现的关键字
  2. 值域不能超过散列表的地址范围
  3. 尽可能减少冲突，散列函数计算出来的地址尽可能均匀分布在整个地址空间
  4. 散列函数应尽量简单，能够快速计算出任一关键字对应的散列地址
除留余数法

除留余数法是一种常见的哈希函数构造方法，它通过取关键字除以一个质数p的余数作为哈希地址（散列表表长为m，取一个不大于m但最接近或等于m的质数p）。这种方法有助于减少哈希冲突的原因主要包括以下几点：

  1. 均匀分布：选择一个适当的质数p作为除数，可以使得哈希地址在整个哈希表中更加均匀地分布，从而降低不同关键字映射到同一地址的概率。
  2. 减少聚簇：由于质数在较小的范围内分布较为均匀，使用质数作为除数可以有效防止数据在哈希表中形成聚簇，即多个数据集中在少数几个桶中，这样可以提高哈希表的空间利用率。
  3. 优化存储效率：通过合理选择质数p，可以使得哈希冲突最小化，即使在数据集很大时也能保持较好的存储效率，减少因冲突引起的额外存储开销。
  4. 简化冲突解决机制：虽然除留余数法不能完全消除冲突，但由于其能够提供较好的初始分布，因此在实际应用中通常配合其他冲突解决策略（如链地址法或开放地址法）来进一步处理剩余的冲突，这些策略在处理较少冲突时更为高效。

除留余数法

直接定址法

直接定址法是一种简单的散列函数设计方法，它将关键字或关键字的某个线性函数值作为散列地址。这种方法适用于关键字长度固定或已知的情况。直接定址法的优点是简单易行，但它的缺点是对于不同的关键字分布情况，冲突率可能较高。在实际应用中，直接定址法虽然简单，但由于其局限性，并不常用。

直接定址法的散列函数通常表示为 h(key)=a×key+b

数字分析法

选取数码分布较为均匀的若干位作为散列地址。设关键字是r进制数（如十进制数），而r个数码在各位上出现的频率不一定相同，可能在某些位上分布均匀一些，每种数码出现的机会均等；而在某些位上分布不均匀，只有某几种数码经常出现，此时可选取数码分布较为均匀的若干位作为散列地址。

平方取中法

平方取中法是一种用于构造散列函数的技术，它通过取关键字的平方值，然后从中提取中间部分作为散列地址。这种方法的优点是散列地址与关键字的每一位都有关联，从而提供了较好的散列地址分布性。当关键字的位数不是很大或者关键字的每一位取值分布不够均匀时，平方取中法特别有效。

在实际应用中，平方取中法首先计算关键字的平方值，然后根据散列表的大小选择适当数量的中间位数作为散列地址。例如，如果散列表的长度为1000，可以选择关键字平方值的中间三位作为散列地址。这种方法适用于不需要预先知道关键字分布情况的场景，因为它通过平方运算自然地扩大了关键字各位的差异，减少了散列冲突的可能性。

平方取中法

散列函数构造方法 使用场景
除留余数法 较为通用，只要关键字是整数即可
直接定址法 关键字分布基本连续
数字分析法 关键字集合已知，且关键字的某几个数码位分布均匀
平方取中法 关键字的每位取值都不够均匀
处理冲突的方法

开放定址法（Open Addressing）是一种解决哈希冲突的方法，用于在哈希表中处理不同关键字映射到同一哈希地址的情况。当发生冲突时，开放定址法会在哈希表中寻找下一个空的存储位置来放置新的元素。这种方法不需要使用额外的数据结构（如链表）来处理冲突，因此在某些情况下可以提供更好的性能和空间利用率。

开放定址法的核心思想是，如果一个给定的哈希地址已经被占用，就依次检查哈希表中的下一个地址，直到找到一个空的位置。这个过程可以通过不同的探测序列来实现，常见的探测序列包括线性探测、平方探测、双散列法和伪随机序列法。线性探测是最简单的方法，它通过在当前地址基础上加上一个增量来寻找下一个地址。平方探测和双重哈希则使用更复杂的函数来计算增量，以减少冲突聚集的可能性。

开放定址法的优点包括简洁的数据结构和较好的缓存局部性，这有助于提高数据访问效率。然而，它也存在一些缺点，如可能导致冲突聚集，特别是当哈希表接近满载时。此外，开放定址法在删除元素时可能会遇到困难，因为直接删除元素可能会破坏哈希表的填充状态，通常需要采用惰性删除或标记已删除的元素来处理。

在实际应用中，开放定址法适用于数据量较小且冲突处理要求较高的场景。开发者需要仔细选择哈希函数和探测策略，以确保哈希表的高效运行.

线性探测法

线性探测法

平方探测法

平方探测法

双散列法

双散列法

伪随机序列法

伪随机序列法

删除元素
  1. 先根据散列函数算出散列地址，并对比关键字是否匹配。若匹配，则查找成功
  2. 若关键字不匹配，则根据探测序列对比下一个地址的关键字，直到查找成功或查找失败
  3. 若查找成功，则删除找到的元素

注意：采用开放定址法时，删除元素不能简单的将被删除的元素空间的位置置为空，否则将截断在它之后的探测路径，可以做一个已删除的标记，进行逻辑删除。删除操作会带来问题，由于是逻辑删除，散列表看起来很满，但实际上很多元素都已经被逻辑删除，此时可以将新元素插入到已被逻辑删除的地址，或者是定期整理散列表内的数据。

探测覆盖率

探测覆盖率