AVL树/B-树/B+树/红黑树
红黑树
1.结点是红色或黑色。
2.根结点是黑色。
3.每个叶子结点都是黑色的空结点（NIL结点）。
4 每个红色结点的两个子结点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色结点)
5.从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点。
插入
新结点（A）位于树根，没有父结点。
- A直接变成黑色
新结点（B）的父结点是黑色。
- A不变
新结点（D）的父结点和叔叔结点都是红色。
- 爸爸叔叔变黑，爷爷变红，然后递归检查
新结点（D）的父结点是红色，叔叔结点是黑色或者没有叔叔，且新结点是父结点的右孩子，父结点（B）是祖父结点的左孩子。
新结点（D）的父结点是红色，叔叔结点是黑色或者没有叔叔，且新结点是父结点的左孩子，父结点（B）是祖父结点的左孩子。
4，5的镜像
删除
如果待删除结点有两个非空的孩子结点，转化成待删除结点只有一个孩子（或没有孩子）的情况。
- 类似二叉树，把右孩子的最大值放过来，并删除这个结点
根据待删除结点和其唯一子结点的颜色，分情况处理。
- 自身是红色，子结点是黑色：
- 直接删
- 自身是黑色，子结点是红色：
- 直接删，子孩子变黑
- 自身是黑色，子结点也是黑色
- 子情况1，结点红黑树的根结点：
- 直接删
- 结点的父亲、兄弟、侄子结点都是黑色：
- 把结点2的兄弟结点B改为红色，递归判断
- 结点2的兄弟结点是红色：
- 子情况1，结点红黑树的根结点：
B-数
乐观锁和悲观锁
乐观并发控制(乐观锁)和悲观并发控制（悲观锁）是并发控制主要采用的技术手段
悲观锁：假定会发生并发冲突，屏蔽一切可能违反数据完整性的操作
- 乐观锁：假设不会发生并发冲突，只在提交操作时检查是否违反数据完整性。
模式（schema）：
模式也称逻辑模式，是数据库全体数据的逻辑结构和特征的描述，是所有用户的公共数据视图。
外模式（external schema）：外模式也称子模式（subschema）或用户模式，它是数据库用户（包括应用程序员和最终用户）能够看见和使用的局部数据的逻辑结构和特征的描述，是数据库用户的数据视图，是与某一应用有关的数据的逻辑表示。
内模式（internal schema）：内模式也称为存储模式（storage schema），一个数据库只有一个内模式。他是数据物理结构和存储方式的描述，是数据库在数据库内部的组织方式。
常用数据模型
层次模型（hierarchical model）
网状模型（network model）
关系模型（relational model）
数据库索引
用于提升数据库的查找速度
顺序索引
- B+ 树索引
比哈希多个排序
- hash 索引
范式
第一范式
属性（字段）是最小单位不可再分
第二范式
满足 1NF，每个非主属性完全依赖于主键
第三范式
满足 2NF，任何非主属性不依赖于其他非主属性
事务
- 是用户定义的一个数据库操作序列，这些操作要么全做，要么全不做，是一个不可分割的工作单位。
事物的 ACID 特性
原子性、一致性、隔离性、持续性
事务是并发控制的基本单位。