Halo

A magic place for coding

0%

实习面经-数据库基础

面试总结之数据库原理基础

  数据库操作是后端开发的基础,数据库的操作涉及到许多实际的细节,以及一些底层的原理,学的时候可能比较凌乱。这里就为大家总结一下常见的考点。总结的部分是结合了教科书、其他面经以及个人的面试经历,相信能够帮助到大家。如果有不足的地方,欢迎大家指出!

  本博客长期更新,欢迎大家收藏、订阅!

索引

为什么要有索引

  如果没有索引,在查询的时候我们就需要全表扫描。使用了index,通过缩小一张表中需要查询的记录、行的数目来加快搜索速度。举个例子,我们查字典很快是因为字典按照字母的顺序排好了,不然的话我们要查一个单词只能够从头一个一个单词看。

索引是什么

  一个索引本身存储两样东西:一是index那一列的值,二是指向表中某一行的指针。这样我们找到这个索引就可以找到这条记录。所以索引是一种数据结构应用。一般会把索引建立在B-Tree上。

索引的分类

  • 哈希索引(hash index):建立在哈希表上的索引,只适用于等值查询,不适合范围查询。因为根据查询值直接哈希就能访问到索引的位置,然后找到表中对应的记录,但是索引本身是无序的,所以没有办法进行范围查询。
  • B-Tree索引:建立在B-Tree上的索引,因为查找、删除、插入操作的时间复杂度都是对数,所以效率很高。同时在B-Tree中的数据是有序的,所以很适合范围查询。
  • 代价:占用空间,凡是插入删除操作都需要及时更新。

什么时候使用索引

  比如我们使用SQL语句查询一个用户SELECT * FROM User WHERE Name = 'John',这个时候数据库会检查Name这个列上是否有索引,如果有,数据库则会检查使用索引是否合理,若合理则使用索引再进行查询。

  咦,这里有个问题,是否合理是如何理解呢?这里牵涉到索引基数和索引选择度问题,详情请移步到传送门


B树和B+树

  两者都应用在数据库索引,可以认为是m叉的多路平衡查找树。数据库索引存储在磁盘上,搜索的时候逐一加载每一个磁盘页(对应索引树的一个结点)。对于树结构而言,IO的次数就是树的高度

  • M阶B树
    1. 定义任意非叶子结点最多只有M个叶子,且$M\gt2$;
    2. 根结点的叶子数为$[2, M]$;
    3. 除根结点外的非叶子结点的叶子数为$[\frac{M}{2}, M]$;
    4. 非叶子结点的key个数=叶子数 - 1;
    5. 所有叶子结点位于同一层;
    6. $k$个key把结点拆成$k+1$段,分别指向$k+1$个儿子,同时满足查找树的大小关系。
  • B树的特点
    1. key集合分布在整棵树中;
    2. 任何一个key出现且只出现在一个结点中;
    3. 搜索有可能在非叶子结点结束;
    4. 其搜索性能等价于在key全集内做一次二分查找
  • M阶B+树特征
    1. 有$n$棵子树的非叶子结点中含有$n$个key(B树是$n-1$个)。这些key本身不存储数据,只用于索引,所有数据都保存在叶子结点。(B树是每个key都保存数据内容);
    2. 所有叶子结点中包含了全部的key,及指向这些key记录的指针。同时,叶子结点本身按照key的大小,从小到大顺序链接成链表;
    3. 所有非叶子结点可以看成是索引部分,结点中仅含其子树中的最大(最小)key;
    4. 通常在B+树上有两个指针,一个指向树结构的根结点,另一个指向key最小的叶子结点,即链表头;
    5. 同一个数字会在不同结点中重复出现,根节点的最大元素就是B+树的最大元素。
  • B+树比B树好在哪?
    1. B+树的中间结点不保存数据本身的内容,所以磁盘页能够容纳更多的key;
    2. B+树查询必须到叶子结点,更加稳定;
    3. 对于范围查找而言,B+树只需要遍历叶子结点链表即可,B树则需要重复地进行遍历。

MyISAM和InnoDB区别

  两者是指MySQL中表的类型。

  • 区别
    1. MyISAM不支持事务处理,InnoDB支持;
    2. MyISAM强调性能,执行速度快;
    3. InnoDB提供事务支持以及外部键等高级功能
  • Details
    1. InnoDB不支持FULLTEXT类型的索引;
    2. InnoDB不保存表的具体行数。执行select count(*) from table时,InnoDB要扫描一遍来计算整个表有多少行,但MyISAM只要读出保存好的行数。当执行count(*)语句时,如果包含where条件时,两种表的操作是一样的;
    3. 对于AUTO_INCREMENT字段,InnoDB中必须包含只有该字段的索引,但是在MyISAM中,可以和其他字段一起建立联合索引;
    4. delete from table时,InnoDB不会重新建表,而是逐行删除;
    5. load table from master对InnoDB无效;
    6. InnoDB表的行锁也不是绝对的。不确定扫描范围时,InnoDB同样会对整个表上锁。

乐观锁与悲观锁

  • 悲观锁:认为数据被并发修改的概率较大,需要在修改之前先加锁。缺点是会产生额外的开销,增加死锁的机会,降低并行性。
    • 基本思路:
      1. 对记录修改前,加上排它锁(exclusive lock)
      2. 若失败,等待或抛出异常
      3. 若成功,允许对记录进行修改,完成后释放锁
    • 实际应用的时候需要关闭数据库的auto_commit
  • 乐观锁:假设数据一般情况下不会造成冲突,所以在数据进行提交更新的时候,才会正式对数据的冲突进行检测。
    • CAS(compare and swap)算法:无锁编程。多个线程使用CAS同时更新同一个变量,只有一个线程能完成更新,其余线程都失败。更新提交的时候,将数据库表对应的记录与第一次取出来的记录作比较。如果相同,则予以更新;否则认为是过期数据,更新失败。
    • ABA问题:CAS算法存在的漏洞,即第一次取出来的记录(A)和当前记录(A)一致,并不能代表数据就是没有被修改过,中间可能存在B,只不过后面又给改回去A了。解决办法是:通过一个单独可顺序递增的version字段(或时间戳),提交时检查版本号和数据的版本号,如果一致才予以更新,version递增。

数据库的隔离级别

隔离级别/问题 脏读 不可重复读 幻读 级别
Read uncommitted
Read committed × 语句级
Repeatable read × × 事务级
Serializable × × × 事务级

数据库连接池

  如果没有使用数据库做过应用开发的话,可能很多人不知道连接池的作用。但是公司的业务肯定会涉及到的,因此还是有必要了解一下。

  • 为什么要用连接池?

    • 简单应用$\rightarrow$数据库访问不频繁$\rightarrow$按需创建连接,用完后关闭
    • 复杂应用$\rightarrow$频繁访问,建立、关闭连接$\rightarrow$减低系统性能(解决办法:连接复用!!
  • 基本原理:在内部对象池中维护一定数量的数据库连接,并对外暴露数据库连接获取和返回方法。如:

    • 获取连接:getConnection()
    • 释放连接:releaseConnection()

    当释放连接的时候,连接并没有真正的关闭,而是由连接池管理器回收,并为下一次使用做好准备。

  • 优点

    1. 资源重用。减少系统开销,增加系统运行环境的平稳性(减少内存碎片、数据库临时进程和线程的数量);
    2. 更快的系统响应速度。因为连接已经初始化,缩短了访问时间;
    3. 更好的资源分配手段。多应用共享同一个数据库,可以通过限制连接数,从而避免某一应用独占所有的数据库资源;
    4. 统一管理:能够很好地避免连接泄漏问题。通过预先设定占用超市,强制收回被占用的连接。

Reference

  1. MySQL存储引擎–MyISAM和InnoDB的区别
  2. 并发控制–乐观锁与悲观锁
  3. 数据库连接池技术详解
  4. 数据库索引是什么

Welcome to my other publishing channels