数据结构 #

树 #

基本概念 #

树有多个节点(node)，用以储存元素
节点之间的连线称为边(edge)
边的上端节点称为父节点
下端称为子节点
树的深度(depth)是从根节点开始（其深度为1）自顶向下逐层累加的
高度的定义为：从结点x向下到某个叶结点最长简单路径中边的条数
深度是从根节点往下

二叉树 #

常见的二叉树：完全二叉树，满二叉树，二叉搜索树，二叉堆，AVL 树，红黑树，哈夫曼树

完全二叉树：若设二叉树的深度为 h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边（效率高）
满二叉树：除最后一层无任何子节点外，每一层上的所有结点都有两个子结点的二叉树
二叉搜索树（二叉排序树，二叉查找树）
- 树中每个节点最多有两个子树，通常称为左子树和右子树
- 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值
- 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值
- 它的左右子树仍然是一棵二叉搜索树 (recursive)
平衡树(B树)
- 排序方式：所有节点关键字是按递增次序排列，并遵循左小右大原则；
- 子节点数：1<非叶节点的子节点数<=M ，且M>=2，空树除外（注：M阶代表一个树节点最多有多少个查找路径，M=M路, 当M=2则是2叉树, M=3则是3叉）
- 关键字数：ceil(m/2)-1<=枝节点的关键字数量<=M-1个（注：ceil()是个朝正无穷方向取整的函数如ceil(1.1)结果为2);
- 所有叶子节点均在同一层、叶子节点除了包含了关键字和关键字记录的指针外也有指向其子节点的指针只不过其指针地址都为null对应下图最后一层节点的空格子
B+树
- 特点
  - B+树的非叶子节点不保存关键字记录的指针，只进行数据索引（非叶子节点所能保存的关键字大大增加）
  - B+树叶子节点保存父节点的所有关键字记录的指针，数据地址必须要到叶子节点才能获取到（每次数据查询的次数都一样）
  - B+树叶子节点的关键字从小到大有序排列，左边结尾数据都会保存右边节点开始数据的指针
  - 非叶子节点的子节点数=关键字数（两种实现，或：非叶节点的关键字数=子节点数-1。Mysql 的B+树是第一种）
- 与红黑树的比较（访问磁盘数据有更高的性能）
  - B+ 树有更低的树高
  - 磁盘访问原理：操作系统一般将内存和磁盘分割成固定大小的块，每一块称为一页，内存与磁盘以页为单位交换数据。数据库系统将索引的一个节点的大小设置为页的大小，使得一次 I/O 就能完全载入一个节点。
    如果数据不在同一个磁盘块上，那么通常需要移动制动手臂进行寻道，而制动手臂因为其物理结构导致了移动效率低下，从而增加磁盘数据读取时间。B+ 树相对于红黑树有更低的树高，进行寻道的次数与树高成正比，在同一个磁盘块上进行访问只需要很短的磁盘旋转时间，所以 B+ 树更适合磁盘数据的读取
  - 为了减少磁盘 I/O 操作，磁盘往往不是严格按需读取，而是每次都会预读。预读过程中，磁盘进行顺序读取，顺序读取不需要进行磁盘寻道，并且只需要很短的磁盘旋转时间，速度会非常快。并且可以利用预读特性，相邻的节点也能够被预先载入
平衡二叉树（AVL 树）：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树
红黑树
- 黑色完美平衡：任意一个结点到到每个叶子结点的路径都包含数量相同的黑结点

缓存淘汰策略LRU( Least Recently Used) #

如果一个数据在最近一段时间没有被访问到，那么在将来它被访问的可能性也很小。也就是说，当限定的空间已存满数据时，应当把最久没有被访问到的数据淘汰。
哈希表+双向链表实现
使用哈希表存储 key，值为链表中的节点，节点中存储值，双向链表来记录节点的顺序，头部为最近访问节点。
**LRU**算法中有两种基本操作
- get(key)：查询key对应的节点，如果key存在，将节点移动至链表头部。
- set(key, value)：设置key对应的节点的值。如果key不存在，则新建节点，置于链表开头。如果链表长度超标，则将处于尾部的最后一个节点去掉。如果节点存在，更新节点的值，同时将节点置于链表头部。