面试题回忆版

墨蓝 2021-12-10 04:41 214阅读 0赞

**1.数据库中索引的优缺点**

> **优点：**  
> （1）通过创建唯一性索引，可以保证数据库表中每一行数据的唯一性。  
> （2）可以大大加快数据的检索速度，这也是创建索引的最主要的原因。  
> （3）可以加速表和表之间的连接，特别是在实现数据的参考完整性方面特别有意义。  
> （4）在使用分组和排序子句进行数据检索时，同样可以显著减少查询中分组和排序的时间。  
> （5）通过使用索引，可以在查询的过程中，使用优化隐藏器，提高系统的性能

In a word：查找快

> **缺点：**  
> （1）创建索引和维护索引要耗费时间，这种时间随着数据量的增加而增加。  
> （2）索引需要占物理空间，除了数据表占数据空间之外，每一个索引还要占一定的物理空间，如果要建立聚簇索引，那么需要的空间就会更大。  
> （3）当对表中的数据进行增加、删除和修改的时候，索引也要动态的维护，这样就降低了数据的维护速度。  
> 原文链接：[https://www.jianshu.com/p/107e5bdf4148][https_www.jianshu.com_p_107e5bdf4148]

一言以蔽之：创建费时间，存储费空间，操作效率低。

**2.数据库中主键和索引的区别**

> （1）主键是为了标识数据库记录唯一性,不允许记录重复,且键值不能为空,主键也是一个特殊索引.  
> （2）数据表中只允许有一个主键,但是可以有多个索引.  
> （3）使用主键会数据库会自动创建主索引,也可以在非主键上创建索引,方便查询效率.  
> （4）索引可以提高查询速度,它就相当于字典的目录,可以通过它很快查询到想要的结果,而不需要进行全表扫描.  
> （5）主键索引外索引的值可以为空.  
> （6）主键也可以由多个字段组成,组成复合主键,同时主键肯定也是唯一索引.  
> （7）唯一索引则表示该索引值唯一,可以由一个或几个字段组成,一个表可以有多个唯一索引.  
> 原文链接：[https://blog.csdn.net/a1037488611/article/details/44264059][https_blog.csdn.net_a1037488611_article_details_44264059]

In another word: 主键是特殊的索引（唯一索引），主键只有一个，索引可以有多个。

**3.数据结构中的查找算法都有哪些**

> **1. 顺序查找**  
> **说明**：顺序查找适合于存储结构为顺序存储或链接存储的线性表。  
> **基本思想**：顺序查找也称为线形查找，属于无序查找算法。从数据结构线形表的一端开始，顺序扫描，依次将扫描到的结点关键字与给定值k相比较，若相等则表示查找成功；若扫描结束仍没有找到关键字等于k的结点，表示查找失败。  
> **复杂度分析**：　  
> **查找成功时的平均查找长度**为：（假设每个数据元素的概率相等） ASL = 1/n(1+2+3+…+n) = (n+1)/2 ; 当查找不成功时，需要n+1次比较，时间复杂度为O(n); 所以，顺序查找的时间复杂度为O(n)。  
> 2.**二分查找**  
> **说明**：元素必须是有序的，如果是无序的则要先进行排序操作。  
> **基本思想**：也称为是折半查找，属于有序查找算法。用给定值k先与中间结点的关键字比较，中间结点把线形表分成两个子表，若相等则查找成功；若不相等，再根据k与该中间结点关键字的比较结果确定下一步查找哪个子表，这样递归进行，直到查找到或查找结束发现表中没有这样的结点。  
> **复杂度分析**：最坏情况下，关键词比较次数为log2(n+1)，且期望时间复杂度为O(log2n)； 注：折半查找的前提条件是需要有序表顺序存储，对于静态查找表，一次排序后不再变化，折半查找能得到不错的效率。但对于需要频繁执行插入或删除操作的数据集来说，维护有序的排序会带来不小的工作量，那就不建议使用。  
> **3.插值查找**  
> **基本思想**：基于二分查找算法，将查找点的选择改进为自适应选择，可以提高查找效率。当然，差值查找也属于有序查找。  
> 注：对于表长较大，而关键字分布又比较均匀的查找表来说，插值查找算法的平均性能比折半查找要好的多。反之，数组中如果分布非常不均匀，那么插值查找未必是很合适的选择。  
> **复杂度分析**：查找成功或者失败的时间复杂度均为O(log2(log2n))。  
> **4.斐波那契查找**  
> **基本思想**：也是二分查找的一种提升算法，通过运用黄金比例的概念在数列中选择查找点进行查找，提高查找效率。同样地，斐波那契查找也属于一种有序查找算法。  
> 　　相对于折半查找，一般将待比较的key值与第mid=（low+high）/2位置的元素比较，比较结果分三种情况：  
> 　　1）相等，mid位置的元素即为所求  
> 　　2）>，low=mid+1;  
> 3）<，high=mid-1。  
> 　　斐波那契查找与折半查找很相似，他是根据斐波那契序列的特点对有序表进行分割的。他要求开始表中记录的个数为某个斐波那契数小1，及n=F(k)-1;  
> 开始将k值与第F(k-1)位置的记录进行比较(及mid=low+F(k-1)-1),比较结果也分为三种  
> 　　1）相等，mid位置的元素即为所求  
> 　　2）>，low=mid+1,k-=2;  
> 　　说明：low=mid+1说明待查找的元素在\[mid+1,high\]范围内，k-=2 说明范围\[mid+1,high\]内的元素个数为n-(F(k-1))= Fk-1-F(k-1)=Fk-F(k-1)-1=F(k-2)-1个，所以可以递归的应用斐波那契查找。  
> 　　3）<，high=mid-1,k-=1。  
> 　　说明：low=mid+1说明待查找的元素在\[low,mid-1\]范围内，k-=1 说明范围\[low,mid-1\]内的元素个数为F(k-1)-1个，所以可以递归 的应用斐波那契查找。  
> **复杂度分析**：最坏情况下，时间复杂度为O(log2n)，且其期望复杂度也为O(log2n)。  
> **5. 树表查找**  
> 　5.1 最简单的树表查找算法——**二叉树查找算法。**  
> 　　基本思想：二叉查找树是先对待查找的数据进行生成树，确保树的左分支的值小于右分支的值，然后在就行和每个节点的父节点比较大小，查找最适合的范围。 这个算法的查找效率很高，但是如果使用这种查找方法要首先创建树。  
> 　5.2 **平衡查找树之2-3查找树（2-3 Tree）**  
> 　　2-3查找树定义：和二叉树不一样，2-3树运行每个节点保存1个或者两个的值。对于普通的2节点(2-node)，他保存1个key和左右两个自己点。对应3节点(3-node)，保存两个Key，2-3查找树的定义如下：  
> 　　1）要么为空，要么：  
> 　　2）对于2节点，该节点保存一个key及对应value，以及两个指向左右节点的节点，左节点也是一个2-3节点，所有的值都比key要小，右节点也是一个2-3节点，所有的值比key要大。  
> 　　3）对于3节点，该节点保存两个key及对应value，以及三个指向左中右的节点。左节点也是一个2-3节点，所有的值均比两个key中的最小的key还要小；中间节点也是一个2-3节点，中间节点的key值在两个跟节点key值之间；右节点也是一个2-3节点，节点的所有key值比两个key中的最大的key还要大。  
> 　　**5.3平衡查找树之红黑树（Red-Black Tree）**  
> 　　2-3查找树能保证在插入元素之后能保持树的平衡状态，最坏情况下即所有的子节点都是2-node，树的高度为lgn，从而保证了最坏情况下的时间复杂度。但是2-3树实现起来比较复杂，于是就有了一种简单实现2-3树的数据结构，即红黑树（Red-Black Tree）。  
> 　　**基本思想**：红黑树的思想就是对2-3查找树进行编码，尤其是对2-3查找树中的3-nodes节点添加额外的信息。红黑树中将节点之间的链接分为两种不同类型，红色链接，他用来链接两个2-nodes节点来表示一个3-nodes节点。黑色链接用来链接普通的2-3节点。特别的，使用红色链接的两个2-nodes来表示一个3-nodes节点，并且向左倾斜，即一个2-node是另一个2-node的左子节点。这种做法的好处是查找的时候不用做任何修改，和普通的二叉查找树相同。  
> **5.4 B树和B+树（B Tree/B+ Tree）**  
> 　　　平衡查找树中的2-3树以及其实现红黑树。2-3树种，一个节点最多有2个key，而红黑树则使用染色的方式来标识这两个key。  
> 　　维基百科对B树的定义为“在计算机科学中，B树（B-tree）是一种树状数据结构，它能够存储数据、对其进行排序并允许以O(log n)的时间复杂度运行进行查找、顺序读取、插入和删除的数据结构。B树，概括来说是一个节点可以拥有多于2个子节点的二叉查找树。与自平衡二叉查找树不同，B树为系统最优化大块数据的读和写操作。B-tree算法减少定位记录时所经历的中间过程，从而加快存取速度。普遍运用在数据库和文件系统。  
> **6.分块查找**  
> 　分块查找又称索引顺序查找，它是顺序查找的一种改进方法。  
> 　　**算法思想**：将n个数据元素"按块有序"划分为m块（m ≤ n）。每一块中的结点不必有序，但块与块之间必须"按块有序"；即第1块中任一元素的关键字都必须小于第2块中任一元素的关键字；而第2块中任一元素又都必须小于第3块中的任一元素，……  
> 　　**算法流程**：  
> 　　step1 先选取各块中的最大关键字构成一个索引表；  
> 　　step2 查找分两个部分：先对索引表进行二分查找或顺序查找，以确定待查记录在哪一块中；然后，在已确定的块中用顺序法进行查找。  
> **7. 哈希查找**  
> 　算法思想：哈希的思路很简单，如果所有的键都是整数，那么就可以使用一个简单的无序数组来实现：将键作为索引，值即为其对应的值，这样就可以快速访问任意键的值。这是对于简单的键的情况，我们将其扩展到可以处理更加复杂的类型的键。  
> 　　算法流程：  
> 　　1）用给定的哈希函数构造哈希表；  
> 　　2）根据选择的冲突处理方法解决地址冲突；  
> 　　　　常见的解决冲突的方法：拉链法和线性探测法。详细的介绍可以参见：浅谈算法和数据结构: 十一 哈希表。  
> 　　3）在哈希表的基础上执行哈希查找。  
> 　　哈希表是一个在时间和空间上做出权衡的经典例子。如果没有内存限制，那么可以直接将键作为数组的索引。那么所有的查找时间复杂度为O(1)；如果没有时间限制，那么我们可以使用无序数组并进行顺序查找，这样只需要很少的内存。哈希表使用了适度的时间和空间来在这两个极端之间找到了平衡。只需要调整哈希函数算法即可在时间和空间上做出取舍。  
> 　　复杂度分析：  
> 　　单纯论查找复杂度：对于无冲突的Hash表而言，查找复杂度为O(1)（注意，在查找之前我们需要构建相应的Hash表）。  
> 　　  
> 　　原文地址：[https://www.cnblogs.com/maybe2030/p/4715035.html][https_www.cnblogs.com_maybe2030_p_4715035.html]

In conclusion:顺序，二分，树，图，分块，哈希

**4.数据库中replace的作用和用法**  
REPLACE(s,s1,s2) 将字符串 s2 替代字符串 s 中的字符串 s1  
将字符串 abc 中的字符 a 替换为字符 x：

SELECT REPLACE('abc','a','x') --xbc

[https_www.jianshu.com_p_107e5bdf4148]: https://www.jianshu.com/p/107e5bdf4148
[https_blog.csdn.net_a1037488611_article_details_44264059]: https://blog.csdn.net/a1037488611/article/details/44264059
[https_www.cnblogs.com_maybe2030_p_4715035.html]: https://www.cnblogs.com/maybe2030/p/4715035.html