# 数据库基础
# 1.数据设计基础
# 2.红黑树
# 2.1.应用场景
- C++中STL中的map,set
- Java中的HashMap
- 维基百科-红黑树的应用 (opens new window)
# 2.2.红黑树笔记
红黑树变色、自旋、自平衡原理
- 本节课的重点是,自旋和变色
- 注意:红黑树新插入的节点『必须』是红色!
- 每个叶子节点都是黑色的空节点(NIL)!
NIL的颜色必须是黑色的,在Java里面,他的值是NULL,因为这个叶子节点是虚拟出来的。
(这个是为了用来满足性质4的)
很显然有2个属性; 1)不能有两个连续的红色
2)红色节点,他必须有父节点,而且这个父节点一定是黑色的。
3)红色节点不能为根节点(性质2),所以红色节点只能为子节点。
- 叶子节点就是上面的,黑色椭圆。
- 红色非平衡和黑色完美平衡(中庸),红黑树是不完美平衡的。
- AVL却是完美平衡。
- 因为左边这样的AVL,不稳定,他这个时候退化为链表了。
新增一个节点,你就要看看这棵树是否违反了我们红黑树的性质,然后,让他自己来平衡。
我们任何新增的红黑树的节点,默认都是新加红色的节点。(因为这个不会影响性质5)
自平衡就是一个调整的过程。
具体的:
你新增的这个节点后,你去编代码的时候,你只需要考虑。从当前节点的三代!!
超过第4代就不管了。
你祖父母都降级了,所以给他一个好处,就是把B节点给他了。
(只要有旋转,就会有一条线互换的。)
旋转节点的圆心,一定是他的子节点!
- 上面的旋转,根本可以不分左边还是右边旋转。
- 下面是红黑树的操作:
CRUD
c-新增
查找很简答--------------
r-读,查找
U-更新(查找到后改就)
D-删除(复杂)
- 上面是我编程的时候的很多case的。
- 上面是做红黑树的所有情况。
直系CPG在一条线上,/或者\
三角关系是,不在一条直线上(也2种)
- 三角关系,其实就是先转换为三点一线关系。
# 3.基础面试题
# 3.1.请你说一下数据库事务以及四个特性
事务(Transaction)
事务(Transaction):是由一系列对系统中数据进行访问与更新的操作所组成的一个程序执行逻辑单元。事务是DBMS中最基础的单位,事务不可分割。『一组原子性的SQL查询』
事务具有4个基本特征,分别是:(简称ACID。)
- 原子性(Atomicity)
- 一致性(Consistency)
- 隔离性( Isolation)
- 持久性(Duration)
# 3.2.详细说一下数据库(Database)中“事务”的4大特征
- 1.原子性(Atomicity)
原子性是指事务包含的所有操作要么全部成功,要么全部失败回滚,因此事务的操作如果成功就必须要完全应用到数据库,如果操作失败则不能对数据库有任何影响。
- 2.一致性(Consistency)
一致性:数据库在事务执行前后都保持一致性状态,在一致性状态下,所有事务对一个数据的读取结果都是相同的。
一致性是指事务必须使数据库从一个一致性状态变换到另一个一致性状态,也就是说一个事务执行之前和执行之后都必须处于一致性状态。拿转账来说,假设用户A和用户B两者的钱加起来一共是5000,那么不管A和B之间 如何转账,转几次账,事务结束后两个用户的钱相加起来应该还得是5000,这就是事务的一致性。
『没有完全理解』
- 3.隔离性(Isolation)
隔离性是当多个用户并发访问数据库时,比如操作同一张表时,数据库为每一个用户开启的事务,不能被其他事务的操作所干扰,多个并发事务之间要相互隔离。
即要达到这么一种效果:对于任意两个并发的事务T1和T2,在事务T1看来,T2要么在T1开始之前就已经结束,要么在T1结束之后才开始,这样每个事务都感觉不到有其他事务在并发地执行。
多个事务并发访问时,事务之间是隔离的,一个事务不应该影响其它事务运行效果。
这指的是在并发环境中,当不同的事务同时操纵相同的数据时,每个事务都有各自的完整数据空间。由并发事务所做的修改必须与任何其他并发事务所做的修改隔离。
不同的隔离级别:
Read Uncommitted(读取未提交内容):
- 最低的隔离级别,什么都不需要做,一个事务可以读到另一个事务未提交的结果。所有的并发事务问题都会发生。脏读
Read Committed(读取提交内容):
- 只有在事务提交后,其更新结果才会被其他事务看见。可以解决脏读问题。不可重复读
Repeated Read(可重复读):
- 在一个事务中,对于同一份数据的读取结果总是相同的,无论是否有其他事务对这份数据进行操作,以及这个事务是否提交。可以解决脏读、不可重复读。
Serialization(可串行化):
- 事务串行化执行,隔离级别最高,牺牲了系统的并发性。可以解决并发事务的所有问题。
完毕
- 持久性(Durability)
持久性是指一个事务一旦被提交了,那么对数据库中的数据的改变就是永久性的,即便是在数据库系统遇到故障的情况下也不会丢失提交事务的操作。
例如我们在使用JDBC操作数据库时,在提交事务方法后,提示用户事务操作完成,当我们程序执行完成直到看到提示后,就可以认定事务以及正确提交,即使这时候数据库出现了问题,也必须要将我们的事务完全执行完成,否则就会造成我们看到提示事务处理完毕,但是数据库因为故障而没有执行事务的重大错误。
# 3.3.请你说一说数据库事务隔离
同一时间,只允许一个事务请求同一数据,不同的事务之间彼此没有任何干扰。比如A正在从一张银行卡中取钱,在A取钱的过程结束前,B不能向这张卡转账。
辅助,解释,上面事物的4大特性
# 3.4.数据库的三大范式
第一范式:当关系模式R的所有属性都不能再分解为更基本的数据单位时,称R是满足第一范式,即属性不可分
第二范式:如果关系模式R满足第一范式,并且R得所有非主属性都完全依赖于R的每一个候选关键属性,称R满足第二范式
第三范式:设R是一个满足第一范式条件的关系模式,X是R的任意属性集,如果X非传递依赖于R的任意一个候选关键字,称R满足第三范式,即非主属性不传递依赖于键码
# 3.5.请你说一说数据库索引
索引是对数据库表中一列
或多列
的值进行排序的一种结构,使用索引可快速访问数据库表中的特定信息。如果想按特定职员的姓来查找他或她,则与在表中搜索所有的行相比,索引有助于更快地获取信息。
索引的一个主要目的就是加快检索表中数据的方法,亦即能协助信息搜索者尽快的找到符合限制条件的记录ID的辅助数据结构。
数据库索引是为了增加查询速度而对表字段附加的一种标识,是对数据库表中一列或多列的值进行排序的一种结构。
DB在执行一条Sql语句的时候,默认的方式是根据搜索条件进行全表扫描,遇到匹配条件的就加入搜索结果集合。如果我们对某一字段增加索引,查询时就会先去索引列表中一次定位到特定值的行数,大大减少遍历匹配的行数,所以能明显增加查询的速度。
# 3.6.请你说一说inner join
和left join
left join(左联接) 返回包括左表中的所有记录和
右表中联结字段相等
的记录right join(右联接) 返回包括右表中的所有记录和
左表中联结字段相等
的记录inner join(等值连接) 只返回两个表中联结字段相等的行
# 3.7.多加索引一定会好吗
- 优点:
通过创建唯一性索引,可以保证数据库表中每一行数据的唯一性。
可以大大加快数据的检索速度,这也是创建索引的最主要的原因。
可以加速表和表之间的连接,特别是在实现数据的参考完整性方面特别有意义。
在使用分组和排序子句进行数据检索时,同样可以显著减少查询中分组和排序的时间。
通过使用索引,可以在查询的过程中,使用优化隐藏器,提高系统的性能。
- 缺点:
创建索引和维护索引要耗费时间,这种时间随着数据量的增加而增加。
索引需要占物理空间,除了数据表占数据空间之外,每一个索引还要占一定的物理空间,如果要建立聚簇索引
,那么需要的空间就会更大。
当对表中的数据进行增加、删除和修改的时候,索引也要动态的维护,这样就降低了数据的维护速度。
# 3.8.添加索引原则
在查询中很少使用或者参考的列不应该创建索引。这是因为,既然这些列很少使用到,因此有索引或者无索引,并不能提高查询速度。相反,由于增加了索引,反而降低了系统的维护速度和增大了空间需求。
只有很少数据值的列也不应该增加索引。这是因为,由于这些列的取值很少,例如人事表的性别列,在查询的结果中,结果集的数据行占了表中数据行的很大比例
,即需要在表中搜索的数据行的比例很大。增加索引,并不能明显加快检索速度。
定义为text
、image
和bit
数据类型的列不应该增加索引。这是因为,这些列的数据量要么相当大,要么取值很少。
当修改性能远远大于检索性能时,不应该创建索引。这是因为,修改性能和检索性能是互相矛盾的。当增加索引时,会提高检索性能,但是会降低修改性能。当减少索引时,会提高修改性能,降低检索性能。因此,当修改性能远远大于检索性能时,不应该创建索引。
# 3.9.请问k-v存储中,key有哪些要求?
- 兴业银行,网上收集的题目
# 3.10.介绍数据库中的WAL技术
- WAL(Write-Ahead Logging,预写式日志)
- 是一种数据安全写入机制。就是先写日志,然后在写入磁盘,这样保证数据的安全性。Mysql中的Redo Log就是采用WAL机制。
- Write-Ahead工作机制:先在内存中提交事务,然后写日志(在InnoDB中就是Redo Log,日志是为了防止宕机导致内存数据丢失),然后再后台任务中把内存中的数据异步刷到磁盘。
WAL优缺点
使用WAL代替回滚日志有其优点和缺点。
优点:
在大多数情况下,WAL的速度要快得多。
WAL提供了更多的并发性,因为读卡器不会阻塞写卡器,而写卡器也不会阻塞读卡器。读和写可以同时进行。
使用WAL,磁盘I/O操作往往更为连续。
WAL使用的fsync()操作更少,因此在fsync()系统调用中断的系统上不易受到问题的攻击
缺点:
一般情况下需要VFS支持共享内存模式(shared-memory primitives)。
操作数据库文件的进程必须在同一台主机上,不能用在网络操作系统。
持有多个数据库文件的数据库连接对于单个数据库时原子的,对于全部数据库是不原子的。
进入WAL模式以后不能修改page的size。
不能打开只读的WAL数据库(Read-Only Databases),这进程必须有"-shm"文件的写权限。
对于只进行读操作,很少进行写操作的数据库,要慢那么1到2个百分点。
会有多余的"-wal"和"-shm"文件。
需要开发者注意checkpointing检查点。
参考:
版权声明:本文为CSDN博主「weixin_39811842」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。 原文链接:https://blog.csdn.net/weixin_39811842/article/details/111509504
# 4.MySQL面试题
# 4.1.请你说一说mysql的四种隔离状态(隔离级别)
Mysql主要包含四种隔离状态:
事务隔离级别 | 脏读 | 不可重复读 | 幻读 |
---|---|---|---|
读未提交(read-uncommitted) | ✅ | ✅ | ✅ |
不可重复读(read-committed) | 否 | ✅ | ✅ |
可重复读(repeatable-read) | 否 | 否 | ✅ |
串行化(serializable) | 否 | 否 | 否 |
# 4.2.请你介绍一下mysql的MVCC机制
MVCC(Multi-Version Concurrency Control,多版本并发控制)
MVCC是一种多版本并发控制机制
是MySQL的InnoDB存储引擎实现隔离级别的一种具体方式,用于实现提交读和可重复读这两种隔离级别。MVCC是通过保存数据在某个时间点的快照来实现该机制,其在每行记录后面保存两个隐藏的列,分别保存这个行的创建版本号和删除版本号,然后Innodb的MVCC使用到的快照存储在Undo日志中,该日志通过回滚指针把一个数据行所有快照连接起来。
# 『学习方法论』
- 分清楚概念中『逻辑上的』和『实现层面上的』
- 将数据结构和算法中的『逻辑结构』和『物理结构』的概念,转移到『数据库』的学习
- 如上:
- 逻辑上有:隔离级别
- 物理实现上有:MVCC啥的
- 优点:将各种术语概念连接在一起,以后就能少被网上层次不齐的资料概念带偏
# 4.3.请问SQL优化方法有哪些
- 1、通过建立索引对查询进行优化
- 2、对查询进行优化,应尽量避免全表扫描『或许这就是我们每个人写SQL语句还分级别的地方』
# 4.4.说一下MySQL引擎的概念和分类
MySQL引擎
MySQL中的数据用各种不同的技术存储在文件(或者内存)中。这些技术中的每一种技术都使用不同的存储机制、索引技巧、锁定水平并且最终提供广泛的不同的功能和能力。通过选择不同的技术,你能够获得额外的速度或者功能,从而改善你的应用的整体功能。
数据库引擎是用于存储、处理和保护数据的核心服务。利用数据库引擎可控制访问权限并快速处理事务,从而满足企业内大多数需要处理大量数据的应用程序的要求。使用数据库引擎创建用于联机事务处理或联机分析处理数据的关系数据库。这包括创建用于存储数据的表和用于查看、管理和保护数据安全的数据库对象(如索引、视图和存储过程)。
MySQL存储引擎主要有:
- MyIsam
- InnoDB
- Memory、Blackhole、CSV、Performance_Schema、Archive、Federated、Mrg_Myisam。
但是最常用的是InnoDB和Mylsam。
# 4.5.说一下最常用的2个MySQL引擎InnoDB和Mylsam的对比
# 1、Mylsam
MyIASM是MySQL默认的引擎,但是它没有提供对数据库事务的支持,也不支持行级锁和外键,因此当INSERT或UPDATE数据时即写操作需要锁定整个表,效率便会低一些。
MyIsam 存储引擎独立于操作系统,也就是可以在windows上使用,也可以比较简单的将数据转移到linux操作系统上去。
适用场景:
不支持事务的设计,但是并不代表着有事务操作的项目不能用MyIsam存储引擎,可以在service层进行根据自己的业务需求进行相应的控制。
不支持外键的表设计。
查询速度很快,如果数据库insert和update的操作比较多的话比较适用。
整天对表进行加锁的场景。
MyISAM极度强调快速读取操作。
MyIASM中存储了表的行数,于是
SELECT COUNT(*) FROM TABLE
时只需要直接读取已经保存好的值而不需要进行全表扫描。如果表的读操作远远多于写操作且不需要数据库事务的支持,那么MyIASM也是很好的选择。
缺点:
- 就是不能在表损坏后主动恢复数据。
索引结构:
MyISAM索引用的B+ tree来储存数据,MyISAM索引的指针指向的是键值的地址,地址存储的是数据。B+Tree的数据域存储的内容为实际数据的地址,也就是说它的索引和实际的数据是分开的,只不过是用索引指向了实际的数据,这种索引就是所谓的非聚集索引。
# 2、InnoDB
InnoDB是一个事务型的存储引擎,有行级锁定和外键约束。
Innodb引擎提供了对数据库ACID事务的支持,并且实现了SQL标准的四种隔离级别,关于数据库事务与其隔离级别的内容请见数据库事务与其隔离级别这类型的文章。该引擎还提供了行级锁和外键约束
它的设计目标是处理大容量数据库系统,它本身其实就是基于MySQL后台的完整数据库系统,MySQL运行时Innodb会在内存中建立缓冲池,用于缓冲数据和索引。但是该引擎不支持FULLTEXT类型的索引,而且它没有保存表的行数,当SELECT COUNT(*) FROM TABLE
时需要扫描全表。当需要使用数据库事务时,该引擎当然是首选。由于锁的粒度更小,写操作不会锁定全表,所以在并发较高时,使用Innodb引擎会提升效率。但是使用行级锁也不是绝对的,如果在执行一个SQL语句时MySQL不能确定要扫描的范围,InnoDB表同样会锁全表。
适用场景:
经常更新的表,适合处理多重并发的更新请求。
支持事务。
可以从灾难中恢复(通过bin-log日志等)。
外键约束。只有他支持外键。
支持自动增加列属性auto_increment。
索引结构:
InnoDB也是B+Tree索引结构。Innodb的索引文件本身就是数据文件,即B+Tree的数据域存储的就是实际的数据,这种索引就是聚集索引。这个索引的key就是数据表的主键,因此InnoDB表数据文件本身就是主索引。
InnoDB的辅助索引数据域存储的也是相应记录主键的值而不是地址,所以当以辅助索引查找时,会先根据辅助索引找到主键,再根据主键索引找到实际的数据。所以Innodb不建议使用过长的主键,否则会使辅助索引变得过大。建议使用自增的字段作为主键,这样B+Tree的每一个结点都会被顺序的填满,而不会频繁的分裂调整,会有效的提升插入数据的效率。
# 3、InnoDB和Mylsam的区别:
比较 | MyIsam | InnoDB |
---|---|---|
事务 | 不支持事务处理等高级处理 | 支持,提供事务支持已经外部键等高级数据库功能 |
性能 | MyISAM类型的表强调的是性能,其执行数度比InnoDB类型更快。 | |
3)行数保存:InnoDB 中不保存表的具体行数,也就是说,执行select count() fromtable时,InnoDB要扫描一遍整个表来计算有多少行,但是MyISAM只要简单的读出保存好的行数即可。注意的是,当count()语句包含where条件时,两种表的操作是一样的。
4)索引存储:对于AUTO_INCREMENT类型的字段,InnoDB中必须包含只有该字段的索引,但是在MyISAM表中,可以和其他字段一起建立联合索引。MyISAM支持全文索引(FULLTEXT)、压缩索引,InnoDB不支持。
MyISAM的索引和数据是分开的,并且索引是有压缩的,内存使用率就对应提高了不少。能加载更多索引,而Innodb是索引和数据是紧密捆绑的,没有使用压缩从而会造成Innodb比MyISAM体积庞大不小。
InnoDB存储引擎被完全与MySQL服务器整合,InnoDB存储引擎为在主内存中缓存数据和索引而维持它自己的缓冲池。InnoDB存储它的表&索引在一个表空间中,表空间可以包含数个文件(或原始磁盘分区)。这与MyISAM表不同,比如在MyISAM表中每个表被存在分离的文件中。InnoDB 表可以是任何尺寸,即使在文件尺寸被限制为2GB的操作系统上。
5)服务器数据备份:InnoDB必须导出SQL来备份,LOAD TABLE FROM MASTER操作对InnoDB是不起作用的,解决方法是首先把InnoDB表改成MyISAM表,导入数据后再改成InnoDB表,但是对于使用的额外的InnoDB特性(例如外键)的表不适用。
MyISAM应对错误编码导致的数据恢复速度快。MyISAM的数据是以文件的形式存储,所以在跨平台的数据转移中会很方便。在备份和恢复时可单独针对某个表进行操作。
InnoDB是拷贝数据文件、备份 binlog,或者用 mysqldump,在数据量达到几十G的时候就相对痛苦了。
6)锁的支持:MyISAM只支持表锁。InnoDB支持表锁、行锁,行锁大幅度提高了多用户并发操作的新能。但是InnoDB的行锁,只是在WHERE的主键是有效的,非主键的WHERE都会锁全表的。
- 因此当表的读操作远远多于写操作,并且不需要事务支持时,可以优先选择MyIasm
# 5.NoSQL类面试题
# 5.1.请你回答一下2种NoSQL的区别mongodb和redis
- 内存管理机制上:
Redis 数据
全部存在内存,定期写入磁盘,当内存不够时,可以选择指定的 LRU 算法删除数据。
MongoDB 数据存在内存,由 linux系统 mmap 实现,当内存不够时,只将热点数据放入内存,其他数据存在磁盘。
- 支持的数据结构上:
Redis 支持的数据结构丰富,包括hash、set、list等。
MongoDB 数据结构比较单一,但是支持丰富的数据表达
,索引,最类似关系型数据库,支持的查询语言非常丰富
# 请你来说一下Redis和memcached的区别?
Memcached是一个自由开源的,高性能,分布式内存对象缓存系统。
Memcached的菜鸟教程 (opens new window)
1)数据类型 :
- redis数据类型丰富,支持set liset等类型;
- memcache支持简单数据类型,需要客户端自己处理复杂对象
2)持久性:
- redis支持数据落地持久化存储;
- memcache不支持数据持久存储。
3)分布式存储:
- redis支持master-slave复制模式;
- memcache可以使用一致性hash做分布式。
4)value大小不同:
- memcache是一个内存缓存,key的长度小于250字符,单个item存储要小于1M,不适合虚拟机使用
5)数据一致性不同:
- redis使用的是单线程模型,保证了数据按顺序提交;
- memcache需要使用cas保证数据一致性。CAS(Check and Set)是一个确保并发一致性的机制,属于“乐观锁”范畴;原理很简单:拿版本号,操作,对比版本号,如果一致就操作,不一致就放弃任何操作
6)cpu利用:
- redis单线程模型只能使用一个cpu,可以开启多个redis进程
# 5.2.请你来说一说Redis的定时机制怎么实现的
Redis服务器是一个事件驱动程序,服务器需要处理以下两类事件:
- 文件事件(服务器对套接字操作的抽象)
- 时间事件(服务器对定时操作的抽象)。Redis的定时机制就是借助时间事件实现的。
一个时间事件主要由以下三个属性组成:
- id:时间事件标识号;
- when:记录时间事件的到达时间;
- timeProc:时间事件处理器,当时间事件到达时,服务器就会调用相应的处理器来处理时间。一个时间事件根据时间事件处理器的返回值来判断是定时事件还是周期性事件
# 5.3.请你来说一说Redis是单线程的,但是为什么这么高效呢?
虽然Redis文件事件处理器以单线程方式运行,但是通过使用I/O多路复用程序来监听多个套接字,文件事件处理器既实现了高性能的网络通信模型,又可以很好地与Redis服务器中其他同样以单线程运行的模块进行对接,这保持了Redis内部单线程设计的简单性。
单个reactor?
# 5.4.请自己设计一下如何采用单线程的方式处理高并发
在单线程模型中,可以采用I/O复用来提高单线程处理多个请求的能力,然后再采用事件驱动模型,基于异步回调来处理事件来
# 5.5.请问Redis的数据类型有哪些,底层怎么实现?
- 1)字符串:整数值、embstr编码的简单动态字符串、简单动态字符串(SDS)
- 2)列表:压缩列表、双端链表
- 3)哈希:压缩列表、字典
- 4)集合:整数集合、字典
- 5)有序集合:压缩列表、跳跃表和字典
# 5.6.请问Redis的rehash怎么做的,为什么要渐进rehash,渐进rehash又是怎么实现的?
因为redis是单线程,当K很多时,如果一次性将键值对全部rehash,庞大的计算量会影响服务器性能,甚至可能会导致服务器在一段时间内停止服务。不可能一步完成整个rehash操作,所以redis是分多次、渐进式的rehash。渐进性哈希分为两种:
- 1)操作redis时,额外做一步rehash
对redis做读取、插入、删除等操作时,会把位于table[dict->rehashidx]位置的链表移动到新的dictht中,然后把rehashidx做加一操作,移动到后面一个槽位。
- 2)后台定时任务调用rehash
后台定时任务rehash调用链,同时可以通过server.hz控制rehash调用频率
# 5.7.请你回答一下hash表如何rehash,以及怎么处理其中保存的资源
C++的hash表中有一个负载因子loadFactor,当loadFactor<=1时,hash表查找的期望复杂度为O(1). 因此,每次往hash表中添加元素时,我们必须保证是在loadFactor <1的情况下,才能够添加。
因此,当Hash表中loadFactor==1时,Hash就需要进行rehash。rehash过程中,会模仿C++的vector扩容方式,Hash表中每次发现loadFactor ==1时,就开辟一个原来桶数组的两倍空间,称为新桶数组,然后把原来的桶数组中元素全部重新哈希到新的桶数组中。
# 5.8.请问Redis怎么实现的定期删除功能
# 5.9.请你说一说Redis对应的命令和数据类型.
key操作常用命令:del,exists,expire,rename
string 操作常用命令:set get incr decr del apend
hash 操作常用命令:hset hget hdel
list 操作常用命令:lpush rpush lpop rpop lset lindex
set 操作常用命令:sadd srem sunion sdiff sinter
zset 操作常用命令:zadd zrem
参考:牛客网