数据库-MySQL
一、数据结构
1、二叉搜索树（BST）
二叉搜索树（BST）又称二叉查找树或二叉排序树。二叉树的提出其实主要就是为了提高查找效率。
特征
1.左子树上所有结点的值均小于或等于它的根结点的值。
2.右子树上所有结点的值均大于或等于它的根结点的值。
3.左、右子树也分别为二叉排序树。
思想
二分查找，查找所需最大次数等同于二叉查找树的高度。
缺点
多次插入新节点会导致二叉树不平衡（如下图所示）。因此就引入了红黑树。
2、红黑树（Red Black Tree）
是一种自平衡的二叉查找树。包含二叉树的基本特性，还有如下特征。
特征
1.节点是红色或黑色。
2.根节点是黑色。
3.每个叶子节点都是黑色的空节点（NIL节点）。
4 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
5.从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
操作调整
为了重新符合红黑树的规则，尝试把红色节点变为黑色，或者把黑色节点变为红色。
左旋转：逆时针旋转红黑树的两个节点，使得父节点被自己的右孩子取代，而自己成为自己的左孩子。
右旋转：顺时针旋转红黑树的两个节点，使得父节点被自己的左孩子取代，而自己成为自己的右孩子。
红黑树的应用
JDK的集合类TreeMap和TreeSet底层就是红黑树实现的，Java8中，HashMap在解决哈希冲突时，当链表长度大于阀值（默认为8）的时候，将链表转化为红黑树，减少搜索时间，ConcurrentHashMap也用到了红黑树。
3、跳表（Skip List）
Skip List是一种随机化的数据结构，基于并联的链表，其效率可比拟于二叉查找树（对于大多数操作需要O(log n)平均时间）。基本上，跳跃列表是对有序的链表增加上附加的前进链接，增加是以随机化的方式进行的，所以在列表中的查找可以快速的跳过部分列表(因此得名)。所有操作都以对数随机化的时间进行。Skip List可以很好解决有序链表查找特定值的困难。
特征
- 一个跳表应该有几个层（level）组成；
- 跳表的第一层包含所有的元素；
- 每一层都是一个有序的链表；
- 如果元素x出现在第i层，则所有比i小的层都包含x；
- 第i层的元素通过一个down指针指向下一层拥有相同值的元素；
- 在每一层中，-1和1两个元素都出现(分别表示INT_MIN和INT_MAX)；
- Top指针指向最高层的第一个元素。
操作
插入操作：
- 新节点和各层索引节点逐一比较，确定原链表的插入位置。O（logN）
- 把索引插入到原链表。O（1）
- 利用抛硬币的随机方式，决定新节点是否提升为上一级索引。结果为“正”则提升并继续抛硬币，结果为“负”则停止。O（logN）
总体上，跳跃表插入操作的时间复杂度是O（logN），而这种数据结构所占空间是2N，既空间复杂度是 O（N）。
删除操作：
- 自上而下，查找第一次出现节点的索引，并逐层找到每一层对应的节点。O（logN）
- 删除每一层查找到的节点，如果该层只剩下1个节点，删除整个一层（原链表除外）。O（logN）
总体上，跳跃表删除操作的时间复杂度是O（logN）。
跳跃表和二叉查找树的比较
跳跃表的优点是维持结构平衡的成本较低，完全依靠随机。二叉查找树在多次插入删除后，需要Rebalance来重新调整结构平衡。
4、B-树（Balance Tree）
B树（B-tree）是一种自平衡的树，能够保持数据有序。这种数据结构能够让查找数据、顺序访问、插入数据及删除的动作，都在对数时间内完成。B树属于多叉树又名平衡多路查找树（查找路径不只两个），数据库索引技术里大量使用者B树和B+树的数据结构。
B- 树的特征（m阶）
1.根结点至少有两个子女。
2.每个中间节点都包含k-1个元素和k个孩子，其中 m/2 <= k <= m
3.每一个叶子节点都包含k-1个元素，其中 m/2 <= k <= m
4.所有的叶子结点都位于同一层。
5.每个节点中的元素从小到大排列，节点当中k-1个元素正好是k个孩子包含的元素的值域分划。
特点
B-树的增加和删除操作比较复杂，但是B-树能够始终维持多路平衡，这也是其一大优势。
应用
主要应用于文件系统以及部分数据库索引，如非关系型数据库MongoDB。
5、B+ 树
B+树是B树的一个升级版，相对于B树来说B+树更充分的利用了节点的空间，让查询速度更加稳定，其速度完全接近于二分法查找。
B+ 树的特征（m阶）
1.有k个子树的中间节点包含有k个元素（B树中是k-1个元素），每个元素不保存数据，只用来索引，所有数据都保存在叶子节点。
2.所有的叶子结点中包含了全部元素的信息，及指向含这些元素记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。
3.所有的中间节点元素都同时存在于子节点，在子节点元素中是最大（或最小）元素。
B+ 树还有一个特点，这个特点是在索引之外的，就是卫星数据的位置。（卫星数据指的是索引元素所指向的数据记录，比如数据库中的某一行）
在B-树中，无论中间节点还是叶子节点都带有卫星数据。而在B+树中，只有叶子节点带有卫星数据，其余中间节点仅仅是索引，没有任何数据关联。
在数据库的聚集索引（Clustered Index）中，叶子节点直接包含卫星数据。在非聚集索引（NonClustered Index）中，叶子节点带有指向卫星数据的指针。
B+ 树优点
1.单一节点存储更多的元素，使得查询的IO次数更少。（因为B+树中间节点没有卫星数据，同样大小的磁盘页可以容纳更多的节点元素）
2.所有查询都要查找到叶子节点，查询性能稳定。（B-树只要找到匹配元素即可，无论匹配元素是处于中间节点还是叶子节点，最好情况只查根节点，最坏情况查到叶子节点，因此不稳定）
3.所有叶子节点形成有序链表，便于范围查询。（B- 树范围查询只能依靠繁琐的中序遍历）
应用
文件系统及数据库系统普遍采用 B+ Tree 作为索引结构。
B+树和红黑树的比较
（1）B+树有更少的查找次数，因为红黑树的树高很明显比 B+ Tree 大非常多，查找的次数也就更多。
（2）B+树能够利用磁盘预读特性。为了减少磁盘 I/O 操作，磁盘往往不是严格按需读取，而是每次都会预读。预读过程中，磁盘进行顺序读取，顺序读取不需要进行磁盘寻道，并且只需要很短的磁盘旋转时间，速度会非常快。操作系统一般将内存和磁盘分割成固定大小的块，每一块称为一页，内存与磁盘以页为单位交换数据。数据库系统将索引的一个节点的大小设置为页的大小，使得一次 I/O 就能完全载入一个节点。并且可以利用预读特性，相邻的节点也能够被预先载入。
二、mysql索引和redis跳表？
他们都是用于解决数据集合的查找问题，即根据指定的key，快速查到它所在的位置（或者对应的value）。
数据集合的查找问题
- 需要支持哪些查找方式，单key/多key/范围查找
- 插入/删除效率
- 查找效率（即时间复杂度）
- 存储大小（空间复杂度）
常用的查找结构：
Hash
hash是key,value形式，通过一个散列函数，能够根据key快速找到value。
B+ Tree
B+树是在平衡二叉树基础上演变过来，B+树首先是有序结构，为了不至于树的高度太高，影响查找效率，在叶子节点上存储的不是单个数据，而是一页数据，提高了查找效率，而为了更好的支持范围查询，B+树在叶子节点冗余了非叶子节点数据，为了支持翻页，叶子节点之间通过指针连接。
跳表
跳表是在链表的基础上进行扩展的，为的是实现redis的Sorted set数据结构。
level0: 是存储原始数据的，是一个有序链表，每个节点都在链上
level0+: 通过指针串联起节点，是原始数据的一个子集，level等级越高，串联的数据越少，这样可以显著提高查找效率，
总结
| 数据结构 | 实现原理 | key查询方式 | 查找效率 | 存储大小 | 插入、删除效率 |
|---|---|---|---|---|---|
| Hash | 哈希表 | 支持单key | 接近O(1) | 小，除了数据没有额外的存储 | O(1) |
| B+树 | 平衡二叉树扩展而来 | 单key,范围，分页 | O(Log(n) | 除了数据，还多了左右指针，以及叶子节点指针 | O(Log(n)，需要调整树的结构，算法比较复杂 |
| 跳表 | 有序链表扩展而来 | 单key，分页 | O(Log(n) | 除了数据，还多了指针，但是每个节点的指针小于<2,所以比B+树占用空间小 | O(Log(n)，只用处理链表，算法比较简单 |
面试反问？
假如我进去后，负责的业务是什么
公司目前技术栈是什么
团队怎么样
您对我这次的面试评价是什么
从面试过程中，您觉得我的优点是什么，不足在什么地方
为什么需要线程池？
提高程序执行的效率可以从两个方面来考虑
- 异步、先响应，返回中间结果，然后异步处理，将结果返回
- 并发，多个线程来执行。
线程池技术使系统复杂了，也提供了更多的灵活性。通过队列的形式，我们将任务的执行拆分成了生产者，消费者模式。每一步只用关心自己的事情。如果我们的任务很复杂，我们可以将任务拆分成不同的步骤，每一步骤可以使用不同的线程池来解决，以此来提高效率。
总结
线程池是一种异步化技术，通过预先创建线程/异步处理来提高响应速度。同时通过统一调配线程资源，可以降低线程的重复创建问题，提高线程的利用率，中心化管理有利于对资源的有效控制，防止滥用。
索引数据结构
数据库索引为什么要使用树结构存储？
查询效率高，可以保持有序。
数据库索引为什么不使用二叉查找树实现？
从算法逻辑上来说，二叉查找树的查询速度和比较次数是最小的，但是需要考虑现实问题，就是磁盘IO的问题，数据库索引是存储在磁盘上的，数据量很大的时候，索引大小就很多，当利用索引查询的时候，我们不能把整个索引加载到内存，能做的只有逐一加载每一个磁盘页，这里的磁盘页对应着索引树的节点。当使用二叉树作为索引节点查询值的时候，在最坏情况下，磁盘IO次数等于索引树的高度，为了减少磁盘IO次数，就需要降低树的高度，所以就要引入B Tree。
未完待续。。。
参考引用：
https://zhuanlan.zhihu.com/p/53975333
