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