导图社区 数据结构查找算法
常用的一些数据结构查找算法，包括b树，b+树等，查找是在数据集合中寻找满足某种条件的数据元素的过程，本图希望对你有帮助。
这是一篇关于操作系统概论的思维导图，OS是指控制和管理整个计算机系统的硬件与软件资源合理的组织、调度计算机的工作与资源分配，进而为用户和其他软件提供方便接口与环境的程序集合。是计算机系统中最基本的系统软件。
一篇关于计算机操作系统IO的一些基本概念，介绍详细、描述全面、希望能对感兴趣的小伙伴学习提供帮助。
数据结构常考排序算法，包括插入排序，希尔排序冒泡排序等几乎所有排序算法，排序是 重新排列表中的元素，使表中的元素满足按关键字递增或递减的过程。
社区模板帮助中心，点此进入>>
互联网9大思维
组织架构-单商户商城webAPP 思维导图。
域控上线
python思维导图
css
CSS
计算机操作系统思维导图
计算机组成原理
IMX6UL(A7)
考试学情分析系统
查找
查找的基本概念
在数据集合中寻找满足某种条件的数据元素的过程
平均查找长度
n为查找表中元素个数 Pi为查找第i个元素的概率，通常假设每个元素查找概率相同，Pi=1/n Ci是找到第i个元素的比较次数。
顺序查找法
一般线性表的顺序查找
有序表的顺序查找
折半查找法
有序的顺序表 （数组）
分块查找法
折半查找和顺序查找的一种改进方法 要求索引表是有序的，块内节点没有排序要求
1、选取各块中的最大关键字构成一个索引表 2、①先对索引表进行折半查找或顺序查找，确定待查记录在哪一块中 ②已确定的块中用顺序法进行查找
B树及其基本操作
B树（多路平衡查找树）
B树的阶（m）：B树中所有结点的孩子结点数的最大值
m阶B树
树中每个结点至多有m棵子树（即至多含有m-1个关键字）
若根结点不是终端结点，则至少有两棵子树
除根节点外的所有非叶结点至少含有 ⌈m/2⌉ 棵子树 （即至少含有 ⌈m/2⌉-1 个关键字）
所有的叶结点都出现在同一层次上，且不带任何信息
B树的高度
n个关键字、高度h、阶数m
B树的查找
B树的插入
1、定位
2、插入
B树的删除
终端结点
非终端结点
B+树的基本概念
⼀棵m阶的B+树需满⾜下列条件： 1）每个分⽀结点最多有m棵⼦树（孩⼦结点）。 2）⾮叶根结点⾄少有两棵⼦树，其他每个分⽀结点⾄少有 棵⼦树。 3）结点的⼦树个数与关键字个数相等。 4）所有叶结点包含全部关键字及指向相应记录的指针，叶结点中将关键字按⼤⼩顺序排列，并且相邻叶结点按⼤⼩顺序相互链接起来。 5）所有分⽀结点中仅包含它的各个⼦结点中关键字的最⼤值及指向其⼦结点的指针。
对比B树与B+树
散列表
基本概念
散列表建立了关键字和存储地址之间的一种直接映射关系，把关键字映射成其对应地址的函数称为散列函数
冲突
散列函数把两个或两个以上的不同关键字映射到同一地址
聚集（堆积）
非同义词争夺一个地址
构造方法
直接定址法
除留余数法
数字分析法
平方取中法
取关键字的平方值的中间几位作为散列地址
折叠法
处理冲突的方法
开放定址法
容易产生聚集
方法
线性探测法
平方探测法
再散列法
伪随机序列法
拉链法（链接法，chaining）
适用于经常进行删除和插入的情况
将冲突的值放在线性链表中
不会产生聚集
散列查找及性能分析
填装因子
填装因子=表中记录数n/散列表长度m
字符串模式匹配
串的定义
零个或多个字符组成的有限序列
串的存储结构
定常顺序存储表示
堆分配存储表示
块链存储表示
串的基本操作
串的模式匹配
KMP
