二叉树
满二叉树，深度为i，总共有pow(2,i) - 1个节点的二叉树称为满二叉树
哈夫曼树：带权路径最短的二叉树称为哈夫曼树或最优二叉树。
终端结点数为n0，度为2的结点数为n2，那么 n0 = n2 + 1
B树
- 根节点至少有两个子节点
- 每个节点有M-1个关键字，并且以升序排列
- 位于M-1和M关键字的子节点的值位于M-1和M关键字对应的Value之间
- 其他节点至少有M/2个子节点
B+树
B+树是对B树的一种变形树，它与B树的差异在于：
- 有k个子结点的结点必然有k个关键码
- 非叶结点仅具有索引作用，跟记录有关的信息均放在叶子结点中。
- 树的所有叶结点构成一个有序链表，可以按照关键码排序的次序遍历全部记录。
B和B+树的区别在于，B+树的非叶子结点只包含导航信息，不包含实际的值，所有的叶子结点和相连的节点使用链表相连，便于区间查找和遍历。
B+ 树的优点在于：
- 由于B+树在内部节点上不包含数据信息，因此在内存页中能够存放更多的key。 数据存放的更加紧密，具有更好的空间局部性。因此访问叶子节点上关联的数据也具有更好的缓存命中率。
- B+树的叶子结点都是相链的，因此对整棵树的遍历只需要一次线性遍历叶子结点即可。而且由于数据顺序排列并且相连，所以便于区间查找和搜索。而B树则需要进行每一层的递归遍历。相邻的元素可能在内存中不相邻，所以缓存命中性没有B+树好。
但是B树也有优点，其优点在于，由于B树的每一个节点都包含key和value，因此经常访问的元素可能离根节点更近，因此访问也更迅速。下面是B树和B+树的区别图：
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-2VcLHveD-1662292694681)(en-resource://database/1121:1)]
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-iPpxUSsP-1662292694683)(en-resource://database/1123:1)]
了解了数据结构再看索引，一切都不费解了，只是顺着逻辑推而已。另加两种存储引擎的区别：
- MyISAM是非事务安全的，而InnoDB是事务安全的
- MyISAM锁的粒度是表级的，而InnoDB支持行级锁
- MyISAM支持全文类型索引，而InnoDB不支持全文索引
- MyISAM相对简单，效率上要优于InnoDB，小型应用可以考虑使用MyISAM
- MyISAM表保存成文件形式，跨平台使用更加方便
- MyISAM管理非事务表，提供高速存储和检索以及全文搜索能力，如果在应用中执行大量select操作可选择
- InnoDB用于事务处理，具有ACID事务支持等特性，如果在应用中执行大量insert和update操作，可选择。
红黑树
解决二叉查找树的线性查找缺点，红黑树主要包括以下五条性质。
- 节点不是红色就是黑色
- 根节点是黑色
- 叶子节点为黑色
- 每个红色节点的两个子结点都是黑色。（从每个叶子节点到跟的所有路径上不能有俩个连续的红色节点）
- 从任意节点到其叶子节点的所有路径都含有相同的黑色节点。
红黑树的插入、删除很可能会破坏红黑树的五条性质，因此需要一些操作来维护红黑树的五条性质不被破坏。主要有三种操作：变色，左旋、右旋。
设计模式
创建型模式共五种： 抽象工厂模式、单例模式、建造者模式、原型模式。
结构型模式共七种： 适配器模式、装饰器模式、代理模式、外观模式、桥接模式、组合模式、享元模式。
行为型模式共十一种： 策略模式、模板方法模式、观察者模式、迭代子模式、责任链模式、命令模式、备忘录模式、状态模式、访问者模式、中介模式、解释器模式。
完全二叉树
编号与满二叉树一致，说明最多是最后一行没有满。
线索二叉树，按照遍历的顺序来找前驱和后驱，前驱看左子树是否为空，后驱看右子树是否为空。
哈夫曼树，先根据最小的两个节点值构造一个根节点，再讲这个根节点放入剩下的节点中，找出最小的两个节点继续构造二叉树，重复以上工作，直至所有节点全部构造完成，规定左子树的边为0，右子树的边为1，得到最终的哈夫曼树。从而得到每个节点的哈夫曼编码。
最小生成树，主要有两种算法，prim算法和kruskal算法，prim算法是每次找出最短的权重边，最后使它联通；kruskal是先找出最短边，然后找比较小的邻接边。
最短路径：迪杰斯特拉（Dijkstra）算法，按路径长度递增的次序产生最短路径的算法。
弗洛伊德算法（Floyd），每次增加一个节点来找最短路径。
拓扑排序：找入度为0的点，找到之后，删除它的所有出度的边，再找一个入度为0的点。
几种排序算法的比较
不稳定排序：快排、堆排序（大根堆、小根堆）、希尔排序（找到两组比较）
稳定：简单排序（插入、冒泡）、归并（相邻两组比较）、基数排序。