跳表

思考

有序链表搜索、添加、删除

时间复杂度较高
二分搜索无法应用

需要搜索、添加、删除快速的数据结构！！

跳表

相比较于红黑树

实现、维护更加简单

跳表：增加多层快速路线

一个node有多层

每层每层都有一个指针
最下层指向下一个节点

实现

import java.util.Comparator;

@SuppressWarnings("unchecked")
public class SkipList<K, V> {
	private static final int MAX_LEVEL = 32;
	private static final double P = 0.25;
	private int size;
	private Comparator<K> comparator;
	/**
	 * 有效层数
	 */
	private int level;
	/**
	 * 不存放任何K-V
	 */
	private Node<K, V> first;
	
	public SkipList(Comparator<K> comparator) {
		this.comparator = comparator;
		first = new Node<>(null, null, MAX_LEVEL);
	}
	
	public SkipList() {
		this(null);
	}
	
	public int size() {
		return size;
	}
	
	public boolean isEmpty() {
		return size == 0;
	}
	
	public V get(K key) {
		keyCheck(key);
		
		// first.nexts[3] == 21节点
		// first.nexts[2] == 9节点
		// first.nexts[1] == 6节点
		// first.nexts[0] == 3节点
		
		// key = 30
		// level = 4
		
		Node<K, V> node = first;
		for (int i = level - 1; i >= 0; i--) {
			int cmp = -1;
			while (node.nexts[i] != null 
					&& (cmp = compare(key, node.nexts[i].key)) > 0) {
				node = node.nexts[i];
			}
			// node.nexts[i].key >= key
			if (cmp == 0) return node.nexts[i].value;
		}
		return null;
	}
	
	public V put(K key, V value) {
		keyCheck(key);
		
		Node<K, V> node = first;
		Node<K, V>[] prevs = new Node[level];
		for (int i = level - 1; i >= 0; i--) {
			int cmp = -1;
			while (node.nexts[i] != null 
					&& (cmp = compare(key, node.nexts[i].key)) > 0) {
				node = node.nexts[i];
			}
			if (cmp == 0) { // 节点是存在的
				V oldV = node.nexts[i].value;
				node.nexts[i].value = value;
				return oldV;
			}
			prevs[i] = node;
		}
		
		// 新节点的层数
		int newLevel = randomLevel();
		// 添加新节点
		Node<K, V> newNode = new Node<>(key, value, newLevel);
		// 设置前驱和后继
		for (int i = 0; i < newLevel; i++) {
			if (i >= level) {
				first.nexts[i] = newNode;
			} else {
				newNode.nexts[i] = prevs[i].nexts[i];
				prevs[i].nexts[i] = newNode;
			}
		}
		
		// 节点数量增加
		size++;
		
		// 计算跳表的最终层数
		level = Math.max(level, newLevel);
		
		return null;
	}
	
	public V remove(K key) {
		keyCheck(key);
		
		Node<K, V> node = first;
		Node<K, V>[] prevs = new Node[level];
		boolean exist = false;
		for (int i = level - 1; i >= 0; i--) {
			int cmp = -1;
			while (node.nexts[i] != null 
					&& (cmp = compare(key, node.nexts[i].key)) > 0) {
				node = node.nexts[i];
			}
			prevs[i] = node;
			if (cmp == 0) exist = true;
		}
		if (!exist) return null;
		
		// 需要被删除的节点
		Node<K, V> removedNode = node.nexts[0];
		
		// 数量减少
		size--;
		
		// 设置后继
		for (int i = 0; i < removedNode.nexts.length; i++) {
			prevs[i].nexts[i] = removedNode.nexts[i];
		}
		
		// 更新跳表的层数
		int newLevel = level;
		while (--newLevel >= 0 && first.nexts[newLevel] == null) {
			level = newLevel;
		}
		
		return removedNode.value;
	}
	
	private int randomLevel() {
		int level = 1;
		while (Math.random() < P && level < MAX_LEVEL) {
			level++;
		}
		return level;
	}
	
	private void keyCheck(K key) {
		if (key == null) {
			throw new IllegalArgumentException("key must not be null.");
		}
	}
	
	private int compare(K k1, K k2) {
		return comparator != null 
				? comparator.compare(k1, k2)
				: ((Comparable<K>)k1).compareTo(k2);
	}
	
	private static class Node<K, V> {
		K key;
		V value;
		Node<K, V>[] nexts;
//		Node<K, V> right;
//		Node<K, V> down;
//		Node<K, V> top;
//		Node<K, V> left;
		public Node(K key, V value, int level) {
			this.key = key;
			this.value = value;
			nexts = new Node[level];
		}
		@Override
		public String toString() {
			return key + ":" + value + "_" + nexts.length;
		}
	}
	
	@Override
	public String toString() {
		StringBuilder sb = new StringBuilder();
		sb.append("一共" + level + "层").append("\n");
		for (int i = level - 1; i >= 0; i--) {
			Node<K, V> node = first;
			while (node.nexts[i] != null) {
				sb.append(node.nexts[i]);
				sb.append(" ");
				node = node.nexts[i];
			}
			sb.append("\n");
		}
		return sb.toString();
	}
}

+ 跳表
    + 初始化
        + node<K,V>：k、v、next[32]（最高）
        + k：comparable
        + head首节点
            + 当前next[]有效层数
    + get（查找）
    	+ 顶层开始，每一层
            + 找到大于目标元素为止！！！
            + 退回到前一个元素
                + 转到下一层
            + 若node值相等，则返回
    + put（添加）
        + 查找前驱节点（插入位置）
        + 创建新节点
            + 设置层数
                + 随机、抛硬币
            + 每层指针修改
                + 查找每层前驱节点
                    + 每个往下走一层的节点！！！（与后面没有其他元素）
                + 每层插入节点指向前驱的后继
                + 每层的前驱指向插入节点
            + 特殊情况（节点高度比全部都高！！！）
                + 首节点响应层数指向插入节点
                + 修改跳表高度
    + remove（删除）
        + 查找每层前驱节点
            + 一直找到最后一层（保证找到每层前驱）
        + 设置前驱节点指向删除节点的后继

跳表的层数

B+树

简介

b树的变体

b树：

平衡多路搜索树
n阶，n个分叉，n-1个节点

+ b+树
    + 分为内部节点和叶子节点
        + 内部节点只存储key，不存储数据
        + 叶子节点存储key和具体数据
    + 所有叶子节点形成一条有序链表！！！

磁盘IO流程

+ 硬盘的分类
    + 固态硬盘
    + 机械硬盘
        + 多个盘片
            + 两个盘面（每个盘片）
                + 一个读写磁头（每个盘面）
                + 磁道（盘面中灰色圆环）
                    + 扇区（每条磁道上的一个弧段）
                        + 磁盘的最小读写单位
                        + 通常512字节、4096字节
                    + 扇区数相同
                    + 外圈扇区面积大，记录数据密度小，浪费空间
        + 存储容量计算
        + 柱面（相同编号的磁道的圆柱）
        + 磁盘块
            + 操作系统最小读写单位（相邻多个扇区的组合）
            + 一般4096字节
            + 操作系统虚拟概念
    + 查看硬盘信息
+ 操作系统读取磁盘数据过程
    + 操作系统将LBA（逻辑块地址：设备、磁头、磁道、扇区）传送给磁盘驱动器并启动读取命令
    + 磁盘驱动器将磁头移动到正确的磁道，盘片开始旋转，将目标扇区旋转到磁头下
    + 磁盘控制器将扇区数据等信息传送到一个处于磁盘界面的缓冲区
    + 磁盘驱动器向操作系统发出“数据就绪”的信号
    + 操作系统从磁盘界面的缓冲区读取数据
+ 磁盘IO时间
    + 寻道时间
        + 操作系统软件层面可以优化
        + 合理安排磁头移动，磁盘调度算法！！！
    + 旋转延迟时间
    + 数据传输时间