查算法【考研408】
高考分数位次怎么查询当采⽤链式存储时，只能顺序查
顺序查
⼀般线性表的顺序查：
若每个元素的查概率相等时，即 =1n
有序表的顺序查：天津市人力资源和社会保障局招聘
查成功同上
折半查
数据必须有序（升序降序都⾏）且顺序存储废除二十一条
搞出来的树是平衡⼆叉树，∴查失败最多为平衡⼆叉树的⾼
h=log2( +1)
分块查
会⼿算模拟即可
块内⽆序，块间有序
索引表中查块：顺序查/折半查
块内查：顺序查/折半查
= + ， ：索引块查 ：块内查
若将长度n的查表均匀分成b块，每块s个记录，等概率下，则
B树和B+树
每个节点内的关键字如果很多 也可以进⾏折半查，因为节点内关键字有序
自考本科条件若每个结点内关键字太少，导致树变⾼，要查更多层结点，效率低（例如只有1个关键字，那就变成了⼆叉查树）↓
如果不平衡，就会导致树很⾼，就要查很多层↓河南省招生办分数查询
策略！规定对于任何⼀个结点，其所有⼦树的⾼度都要相同
核⼼特性
计算B树⾼度时，不包含失败节点（叶⼦结点）
n个关键字的m阶B树的最⼩最⼤⾼度↓
最⼩⾼度：
最⼤⾼度：
—— —— B树 ↑ —— —— —— —— —— —— —— —— B+树 ↓ —— —— —— —— —— —— —— ——
注：以上是⼀棵4阶B+树
B+树中索引结点为保留的最⼤关键字
B+树的前⾯只索引，只有在到叶⼦结点之后才知道这个记录在哪，才能结束查，所以B+树中，⽆论查成功与否，最终⼀定都要⾛到最下⾯⼀层结点
B+树⽀持顺序查
⼀棵m阶的B+树需满⾜下列条件:
1）每个分⽀结点最多有m棵⼦树(孩⼦结点)
3）结点的⼦树个数与关键字个数相等。
4）所有叶结点包含全部关键字及指向相应记录的指针，叶结点中将关键字按⼤⼩顺序排列，并且相邻叶结点按⼤⼩顺序相互链接起来
5）所有分⽀结点中仅包含它的各个⼦结点中关键字的最⼤值及指向其⼦结点的指针。
2023年省考成绩公布时间因为B树和B+树的结点都是放在磁盘的块中，所以每弄⼀个结点都需要拿⼀块，因为B树的结点要放记录，⽽B+数的结点仅索引，所以B数的结点需要的内存更⼤，⽽磁盘速度慢，所以B树需要耗费更⼤的时间
所以，B+树适合关系型数据库索引
发布评论