您的位置: 首页 > 面试技巧

面试题:索引有哪些,数据结构是什么,区别是什么?

来源:  |  发布时间:2021-08-12  |  浏览量:452

面试题:索引有哪些,数据结构是什么,区别是什么?

普通索引

唯一索引:唯一索引是不允许其中任何两行具有相同索引值的索引

主键索引:数据库表经常有一列或列组合,其值唯一标识表中的每一行。该列称为表的主键。

聚集索引:表中行的物理顺序与键值的逻辑(索引)顺序相同

非聚集索引:数据库表中记录的物理顺序与索引顺序可以不相同

索引的实现通常使用B树及其变种B+树。

1)B树

B树中每个节点包含了键值和键值对于的数据对象存放地址指针,所以成功搜索一个对象可以不用到达树的叶节点。

成功搜索包括节点内搜索和沿某一路径的搜索,成功搜索时间取决于关键码所在的层次以及节点内关键码的数量。

在B树中查找给定关键字的方法是:首先把根结点取来,在根结点所包含的关键字K1,…,kj查找给定的关键字(可用顺序查找或二分查找法),若找到等于给定值的关键字,则查找成功;否则,一定可以确定要查的关键字在某个Ki或Ki+1之间,于是取Pi所指的下一层索引节点块继续查找,直到找到,或指针Pi为空时查找失败。


2)B+树

B+树非叶节点中存放的关键码并不指示数据对象的地址指针,非也节点只是索引部分。所有的叶节点在同一层上,包含了全部关键码和相应数据对象的存放地址指针,且叶节点按关键码从小到大顺序链接。如果实际数据对象按加入的顺序存储而不是按关键码次数存储的话,叶节点的索引必须是稠密索引,若实际数据存储按关键码次序存放的话,叶节点索引时稀疏索引。

B+树有2个头指针,一个是树的根节点,一个是最小关键码的叶节点。

所以 B+树有两种搜索方法:

一种是按叶节点自己拉起的链表顺序搜索。

一种是从根节点开始搜索,和B树类似,不过如果非叶节点的关键码等于给定值,搜索并不停止,而是继续沿右指针,一直查到叶节点上的关键码。所以无论搜索是否成功,都将走完树的所有层。

B+ 树中,数据对象的插入和删除仅在叶节点上进行。

这两种处理索引的数据结构的不同之处:

a,B树中同一键值不会出现多次,并且它有可能出现在叶结点,也有可能出现在非叶结点中。而B+树的键一定会出现在叶结点中,并且有可能在非叶结点中也有可能重复出现,以维持B+树的平衡。

b,因为B树键位置不定,且在整个树结构中只出现一次,虽然可以节省存储空间,但使得在插入、删除操作复杂度明显增加。B+树相比来说是一种较好的折中。

c,B树的查询效率与键在树中的位置有关,最大时间复杂度与B+树相同(在叶结点的时候),最小时间复杂度为1(在根结点的时候)。而B+树的时候复杂度对某建成的树是固定的。


相关新闻

24小时报名热线

400-7777-699

报名热线:400-7777-699

微博

微信公众号

友情链接 :智原在线   美味学院   安徽新华电脑   安徽新华教育

华信智原(官网)|京ICP备09028087号-8|咨询热线:400-7777-699|地址:北京海淀区北三环中路44号院爱工场文化教育产业园|版权所有:北京华信智原教育技术有限公司
在线报名 学费详情 开班信息 职业护航 视频下载

小小华想和您聊一聊