算法篇 — B 树 、 B+ 树 和 B* 树
基础概念
二叉树，只有一个根节点，每个树节点最多有两个子节点，允许有多层级节点。二叉树查找平均时间复杂度 O(logn)，但最坏查找次数依赖于二叉树的深度，最坏查找时间复杂度 O(n) 即所有节点偏向左或右。
完全二叉树，所有叶子结点都出现在 K 或 K-1 层，而且从 1 到 k-1 层每层都是满节点数。最多只有 K 层不是满节点数，且非满节点的 K 层集中在左边。查找平均时间复杂度 O(logn) 、最坏查找时间复杂度 O(logn)。
平衡二叉树，保证左右子树的高度之差不大于 1，并且子树也必须是一颗平衡二叉树。当添加或删除节点时需要通过旋转保持整个数的平衡。最终，插入、查找的时间复杂度 O(logn)。
B 树
是一个平衡的多路查找树，平衡二叉树的变种。一个 m 阶的 B 树需要满足，(1) 树中每个节点至多有 m 个子树 (m>2)。（2）每个非叶子节点（除根节点）最少有⌈m/2⌉ 个子节点，⌈m/2⌉ 表示向上取整。（3）如果根节点不是叶子节点，那么它至少有 2 个子节点。（4）有 K 个子结点的非叶子节点拥有 K-1 个键。（5）所有叶子结点都在同一层。（5）树节点上包含数据部分和子结点地址链接部分。
因为树节点上包含了关键字及数据，也就查询时间平均和最坏耗时 O(logn) 。但并不稳定，因为依据查询数据可能会使用更少次数就能查询到。这咋听之下是好事，但因为节点不止包含关键字还包含了数据，也就是一次磁盘 IO 读取可能只却出一个节点，但节点上可以包含的关键字数会有限制且较少，也就是磁盘 IO 读取次数会多。
B+ 树
B+ 树是 B 树的变种，B+ 树上非叶子节点不保存数据，只用来保存索引字段值。这样确保一个节点上能保存更多的索引字段值，让整颗树的高度相对于 B 树更低。因为叶子节点上是数据节点，也就是所有的搜索都会落到叶子节点上，所以搜索耗时保持 O(logn) 。而对于全数据遍历时，因为 B+ 树叶子节点有一个指针指向下一个节点，把所有叶子节点串在一起。B+ 树只需要遍历叶子结点链表，B 树需要复杂的中序遍历。
B * 树
B* 树是 B+ 树的变种。在 B+ 树的基础上在非根和非叶子节点再增加指向兄弟的指针。因为设置了兄弟的指针，所以在增加数据节点本树节点满时，B* 树会看兄弟节点是否有空位，有的话就会把数据节点加在兄弟节点上。兄弟节点也没有空间的话，则在原节点与兄弟节点之间增加新节点，并各复制1/3的数据到新节点，最后在父节点增加新节点的指针。而 B+ 树当一个节点满时，分配一个新的节点，并将原节点中1/2的数据复制到新节点，最后在父节点中增加新结点的指针；B+树的分裂只影响原节点和父节点，而不会影响兄弟节点。B* 树分配新接点的概率比 B+ 树要低，空间使用率更高。
索引的离散型
count(distinct column_name):count(*)比值越高，差别值占比越高，索引效率越高。
