ARTS （第23周）

触类旁通

换个思路，一切就都将不一样

本周：

B+树、A*算法

Algorithm 算法

B+树

是一种树结构的数据，利用节点的分裂合并来达到自动平衡的效果。

查找和插入的性能都是logn，除此之外最大的优势是适合区间查找，以及是个多叉树的结构，适合储存进磁盘当索引使用。

package algorithm.senior.bplustree;

import java.util.Arrays;
import java.util.HashSet;

import algorithm.util.RandomUtil;

public class BPlusTree {
	/////////////////////////
	//测试
	///////////////////////////
	public static void main(String[] args) {
		testRange();
		testRange2();
		test();// mark TODO
	}
	private static void testRange() {
		BPlusTree t = new BPlusTree();
		int num = 100;// 随机数范围
		for (int i = 0; i < num; i++) {
			t.add(i);
		}
		System.out.println("all:" + Arrays.toString(t.toArray()));
		int s = RandomUtil.randomNum(num);
		int e = RandomUtil.randomNum(num);
		System.out.println("s:" + s + ",e:"+e);
		if(e<s){
			//也可以用相加交换的方式 和这个思路一致
			s^=e;
			e^=s;
			s^=e;
			System.out.println("swap->s:" + s + ",e:"+e);
		}
		int[] array1 = t.findRange(s, e);//
		System.out.println("range:" + Arrays.toString(array1));
		
	}
	private static void testRange2() {
		BPlusTree t = new BPlusTree();
		int rdNum = 15;// 随机数量
		int num = 100;// 随机数范围
		int size = RandomUtil.randomNum(rdNum)+rdNum;
		// size = 1;
		System.out.print("add:");
		for (int i = 0; i < size; i++) {
			int rd = RandomUtil.randomNum(num);
			System.out.print(rd + ",");
			t.add(rd);
		}
		System.out.println();
		System.out.println("all:" + Arrays.toString(t.toArray()));
		int s = RandomUtil.randomNum(num);
		int e = RandomUtil.randomNum(num);
		System.out.println("s:" + s + ",e:"+e);
		if(e<s){
			//也可以用相加交换的方式 和这个思路一致
			s^=e;
			e^=s;
			s^=e;
			System.out.println("swap->s:" + s + ",e:"+e);
		}
		int[] array1 = t.findRange(s, e);//
		System.out.println("range:" + Arrays.toString(array1));
		
	}
	
	// 测试用的属性
	static StringBuffer str = new StringBuffer();
	// 测试用的属性
	static int c = 0;

	private static void test() {
		BPlusTree t = new BPlusTree();
		HashSet<Integer> set = new HashSet<Integer>();

		int size = 0;
		str = new StringBuffer();
		c = 0;
		int rdNum = 5;// 每次的随机数
		int num = 3000000;// 随机数范围
		while (true) {
			System.out.println("===========================");
			// 随机加N个
			size = RandomUtil.randomNum(rdNum);
			// size = 1;
			System.out.print("add:");
			for (int i = 0; i < size; i++) {
				int rd = RandomUtil.randomNum(num);
				System.out.print(rd + ",");
				t.add(rd);
				set.add(rd);
				str.append("t.add(" + rd + ");");
				c++;
			}
			System.out.println();
			System.out.println(t.h);
			System.out.print("del:");
			// 随机删N个
			size = RandomUtil.randomNum(rdNum);
			// size = 1;
			for (int i = 0; i < size; i++) {
				int rd = RandomUtil.randomNum(num);
				if (!set.contains(rd)) {
					// continue;
				}
				System.out.print(rd + ",");
				t.remove((Integer) rd);
				set.remove((Integer) rd);
				str.append("t.remove(" + rd + ");");
				c++;
			}
			System.out.println();
			System.out.println(t.h);
			// 比较
			int[] array2 = new int[set.size()];
			int idx = 0;
			for (Integer ix : set) {
				array2[idx++] = ix;
			}
			Arrays.sort(array2);
			// int[] array1 = t.toArray2();
			// int[] array1 = t.toArray2();
			int[] array1 = t.findRange(-1, num + 1);//全部
			System.out.println("size:" + t.getSize());
			System.out.println("arr2:" + Arrays.toString(array2));
			System.out.println("arr1:" + Arrays.toString(array1));
			for (int i = 0; i < array2.length; i++) {
				if (array2[i] != array1[i] || array1.length != array2.length) {
					System.out.println("err");
					System.out.println("出现异常的指令数量:" + c);
					System.out.println("异常过程->" + str);
					System.exit(0);
					// if (c < 15) {//
					// System.exit(0);
					// } else {
					// test();
					// }
				}
			}
			try {
				// Thread.sleep(500);
			} catch (Exception e) {
				e.printStackTrace();
			}
		}
	}

	public static void printTest(BPlusTree t) {
		System.out.println(t.h);
		System.out.println(Arrays.toString(t.toArray2()));
	}

	// 测试 k v相同
	public void add(int k) {
		add(k, k);
	}
	
	/////////////////////////////////////////////////////////////////
	////////实际算法部分 
	//////////////////////////////////////////////////////////////
	private BPlusTreeNode h;// 根
	private int s;// 当前元素个数
	// 开始位置和结束 (包含边界)
	// s<= n =>e
	public int[] findRange(int s, int e) {
		if (this.s == 0) {
			return new int[0];
		}
		Node curr = h;
		// 查找已有元素 直到叶子节点 或者当前节点比 开始值更小
		while (curr instanceof BPlusTreeNode) {
			BPlusTreeNode node = (BPlusTreeNode) curr;
			int idx = 0;
			while (idx < node.size - 1 && s > node.keywords[idx]) {
				idx++;
			}

			curr = node.children[idx];
		}
		// 找到叶子节点
		BPlusTreeLeafNode leaf = (BPlusTreeLeafNode) curr;
		int idx = 0;
		for (int i = 0; i < leaf.size; i++) {
			// 找到在叶子节点里的开始位置
			if (s > leaf.keywords[idx]) {
				idx++;
				//break;
			}
		}
		BPlusTreeLeafNode c = leaf;
		// 链表头是个哨兵 不保存东西 不然语义不清晰
		SmallLinkedNode head = new SmallLinkedNode();
		SmallLinkedNode linkedNode = head;
		int size = 0;
		while (c != null) {
			for (int i = idx; i < c.size; i++) {
				if (c.keywords[i] > e) {
					break;
				}
				linkedNode = linkedNode.setNext(c.keywords[i]);
				size++;
			}
			// 下个节点继续
			c = c.next;
			idx = 0;
		}
		// 链表转数组
		int[] r = new int[size];
		linkedNode = head;
		int ix = 0;
		while (linkedNode.next != null) {
			linkedNode = linkedNode.next;
			r[ix++] = linkedNode.k;
		}
		return r;
	}

	public BPlusTree() {
		s = 0;
		h = new BPlusTreeNode();// 根
	}
	//父级到子级的连接正确的话 这里的返回是正确的
	public int[] toArray() {
		if (s == 0) {
			return new int[0];
		}
		int[] r = new int[s];
		h.fillArr(r, 0);
		return r;
	}
	//
	public int[] toArray2() {
		if (s == 0) {
			return new int[0];
		}
		int i = 0;
		int[] r = new int[s];
		Node curr = h;
		while (curr instanceof BPlusTreeNode) {
			BPlusTreeNode node = (BPlusTreeNode) curr;
			curr = node.children[0];
		}
		BPlusTreeLeafNode cur = (BPlusTreeLeafNode) curr;
		while (cur != null) {
			for (int j = 0; j < cur.size; j++) {
				r[i++] = cur.keywords[j];
			}
			cur = cur.next;
		}

		return r;
	}

	public void add(int k, long v) {
		if (s == 0) {
			BPlusTreeLeafNode leaf = new BPlusTreeLeafNode();
			leaf.parent = h;
			h.children[0] = leaf;
			h.keywords[0] = k;
			h.size++;
			leaf.add(k, v);
			s++;
			return;
		}
		Node curr = h;
		// 查找已有元素 直到叶子节点
		while (curr instanceof BPlusTreeNode) {
			int idx = 0;
			BPlusTreeNode node = (BPlusTreeNode) curr;
			while (idx < node.size - 1 && k > node.keywords[idx]) {
				idx++;
			}
			curr = node.children[idx];
		}
		// 找到叶子节点
		BPlusTreeLeafNode leaf = (BPlusTreeLeafNode) curr;
		if (leaf.add(k, v)) {
			s++;
		}
		leaf.check();
	}

	public boolean contains(int k) {
		if (s == 0) {
			return false;
		}

		Node curr = h;
		// 查找已有元素 直到叶子节点
		while (curr instanceof BPlusTreeNode) {
			int idx = 0;
			BPlusTreeNode node = (BPlusTreeNode) curr;
			while (idx < node.size - 1 && k > node.keywords[idx]) {
				idx++;
			}
			curr = node.children[idx];
		}
		// 找到叶子节点
		BPlusTreeLeafNode leaf = (BPlusTreeLeafNode) curr;
		return leaf.exists(k) != -1;
	}

	public void remove(int k) {
		if (s == 0) {
			return;
		}

		Node curr = h;
		// 查找已有元素 直到叶子节点
		while (curr instanceof BPlusTreeNode) {
			int idx = 0;
			BPlusTreeNode node = (BPlusTreeNode) curr;
			while (idx < node.size - 1 && k > node.keywords[idx]) {
				idx++;
			}
			curr = node.children[idx];
		}
		// 找到叶子节点
		BPlusTreeLeafNode leaf = (BPlusTreeLeafNode) curr;
		if (leaf.remove(k)) {
			s--;
		}
		leaf.check();
	}

	public int getSize() {
		return s;
	}

	/////////////////////////////////////////////////////////////
	// 这里的K值和M值都是经过计算之后的磁盘的1个页的大小来计算的，计算方式下面有罗列
	// 这里是假设1页是4kb(按目前来说,正常情况下一般也是4kb居多)也可以通过磁盘的其它单位来查找
	// 这里因为是int类型是写死了k和m，
	// 在数据库中可能是根据索引列的类型、结合系统指令获取磁盘的参数后进行计算的。
	/////////////////////////////////////////////////////////////
	/**
	 * 这是 B+ 树非叶子节点的定义。
	 *
	 * 假设 keywords=[3, 5, 8, 10] 4 个键值将数据分为 5 个区间：(-INF,3), [3,5), [5,8),
	 * [8,10), [10,INF) 5 个区间分别对应：children[0]...children[4]
	 *
	 * m 值是事先计算得到的，计算的依据是让所有信息的大小正好等于页的大小： PAGE_SIZE = (m-1)*4[keywordss
	 * 大小]+m*8[children 大小]
	 */
	public class BPlusTreeNode extends Node {
		public int m = 5; // 5 叉树
		// 每个子节点保存的值 内容如下
		// 这里的节点和值的对应关系为
		// 小于当前节点key 大于等于前一个节点key
		// 第一个和最后一个 没有前一个节点或者最后一个阶段的时候 就不用管
		public Node[] children;// 保存子节点指针

		public BPlusTreeNode() {
			keywords = new int[m]; // 键值，用来划分数据区间
			children = new Node[m];// 保存子节点指针
		}

		@Override
		public int fillArr(int[] r, int idx) {
			for (int i = 0; i < size; i++) {
				idx = children[i].fillArr(r, idx);
			}
			return idx;
		}

		@Override
		public String toString() {
			return "{ \"size\":" + size + ", \"keywords\":" + printArr(keywords, size) + ", \"children\":"
					+ printArr(children, size) + "}";
		}

		public void add(Node o, Node n) {
			int idx = 0;
			for (; idx < children.length; idx++) {
				if (children[idx] == o) {
					break;
				}
			}
			// 更新节点
			moveRight(idx);
			keywords[idx] = o.keywords[o.size - 1];
			keywords[idx + 1] = n.keywords[n.size - 1];
			children[idx + 1] = n;
			size++;
			// 不需要分裂
			if (size < m) {
				return;
			}
			// 需要分裂
			size = size / 2;// 一半
			// 分裂新节点
			BPlusTreeNode node = new BPlusTreeNode();
			// 关联
			for (int i = size; i < this.m; i++) {
				children[i].parent = node;
			}
			node.size += this.m - size;
			// 复制属性
			System.arraycopy(keywords, size, node.keywords, 0, node.size);
			System.arraycopy(children, size, node.children, 0, node.size);
			// 新父级
			if (parent == null) {
				parent = new BPlusTreeNode();
				parent.children[parent.size] = this;
				parent.keywords[parent.size++] = this.keywords[this.size - 1];
				h = parent;
			}
			// 关联
			node.parent = parent;
			// 父级判断
			parent.add(this, node);
		}

		/**
		 * 指定IDX的左移(等同于删掉指定IDX)
		 */
		private void moveLeft(int idx) {
			// size - 1 - idx 为当前节点右边的元素数量（不含自己）
			System.arraycopy(keywords, idx + 1, keywords, idx, size - 1 - idx);
			System.arraycopy(children, idx + 1, children, idx, size - 1 - idx);
		}

		/**
		 * 指定IDX的右移(将IDX的位置让出来，方便插入)
		 */
		private void moveRight(int idx) {
			// size - idx 为当前节点以及当前节点右边的元素数量（含自己）
			System.arraycopy(keywords, idx, keywords, idx + 1, size - idx);
			System.arraycopy(children, idx, children, idx + 1, size - idx);
		}

		// 合并或者借或者删除自己
		private void merge() {
			if (parent == null) {
				resetHead();
				return;
			}
			int idx = 0;
			// 找到自己在父级的索引
			for (; idx < parent.children.length; idx++) {
				if (parent.children[idx] == this) {
					break;
				}
			}

			// 当前节点没东西了
			if (size == 0) {
				parent.moveLeft(idx);
				parent.size--;
				parent.merge();
				return;
			}
			// 判断是否需要合并 或者借节点
			if (size >= m / 2) {
				return;// 不需要
			}
			// 借或者取 然后要更新keyword
			if (idx > 0 && parent.children[idx - 1].size - 1 > m / 2) {
				// 前节点借
				int bIdx = idx - 1;
				BPlusTreeNode b = (BPlusTreeNode) parent.children[bIdx];
				moveRight(0);
				// 把兄弟节点的最后一个元素拿过来
				keywords[0] = b.keywords[--b.size];
				children[0] = b.children[b.size];
				children[0].parent = this;
				size++;
				// 刷新key
				parent.refreshKey(bIdx);
			} else if (idx > 0 && parent.children[idx - 1].size + size < m) {
				// 前节点合并
				int bIdx = idx - 1;
				BPlusTreeNode b = (BPlusTreeNode) parent.children[bIdx];
				// 重新关联父级关系
				for (int i = 0; i < size; i++) {
					children[i].parent = b;
				}
				// 将当前节点的东西都转移到前节点 刷新key
				System.arraycopy(children, 0, b.children, b.size, size);
				System.arraycopy(keywords, 0, b.keywords, b.size, size);
				//
				b.size += size;
				parent.moveLeft(idx);// 删除自己
				parent.refreshKey(bIdx);// 刷新key
				parent.size--;
				parent.merge();
			} else if (idx < parent.size - 1 && parent.children[idx + 1].size - 1 > m / 2) {
				// 后节点借
				int bIdx = idx + 1;
				BPlusTreeNode b = (BPlusTreeNode) parent.children[bIdx];
				keywords[size] = b.keywords[0];
				children[size] = b.children[0];
				children[size++].parent = this;
				b.moveLeft(0);
				b.size--;
				parent.refreshKey(idx);// 刷新自己
			} else if (idx < parent.size - 1 && parent.children[idx + 1].size + size < m) {
				// 后节点合并
				int bIdx = idx + 1;
				BPlusTreeNode b = (BPlusTreeNode) parent.children[bIdx];
				// 重新关联父级关系
				for (int i = 0; i < b.size; i++) {
					b.children[i].parent = this;
				}
				System.arraycopy(b.children, 0, children, size, b.size);
				System.arraycopy(b.keywords, 0, keywords, size, b.size);
				size += b.size;
				// 刷新
				parent.refreshKey(idx);
				parent.moveLeft(bIdx);
				parent.size--;
				parent.merge();
			} else {
				parent.refreshKey(idx);
			}

		}

		private void resetHead() {
			// 如果子节点的所有子节点加起来小于m 就进行合并然后替换head
			int count = 0;
			for (int i = 0; i < size; i++) {
				count += children[i].size;
			}
			// 不替换head的情况
			// 没有子节点、太多子节点、或者子节点是叶子节点
			if (count == 0 || count >= m || children[0] instanceof BPlusTreeLeafNode) {
				return;
			}
			BPlusTreeNode newHead = (BPlusTreeNode) children[0];
			// 从第二个节点开始将东西放入第一个节点
			for (int i = 1; i < size; i++) {
				BPlusTreeNode node = (BPlusTreeNode) children[i];
				for (int j = 0; j < node.size; j++) {
					node.children[j].parent = newHead;
				}
				System.arraycopy(node.children, 0, newHead.children, newHead.size, node.size);
				System.arraycopy(node.keywords, 0, newHead.keywords, newHead.size, node.size);
				newHead.size += node.size;
			}
			newHead.parent = null;
			// 重置根节点
			h = newHead;
		}

		private void refreshKey(int idx) {
			keywords[idx] = children[idx].keywords[children[idx].size - 1];
			if (idx == size - 1 && parent != null) {
				idx = 0;
				// 找到自己在父级的索引
				for (; idx < parent.children.length; idx++) {
					if (parent.children[idx] == this) {
						break;
					}
				}
				parent.refreshKey(idx);
			}
		}

		private void refresh() {
			if (parent == null)
				return;
			int idx = 0;
			// 找到自己在父级的索引
			for (; idx < parent.children.length; idx++) {
				if (parent.children[idx] == this) {
					break;
				}
			}
			parent.refreshKey(idx);
		}

	}

	public abstract class Node {
		public int size;// 大小
		public BPlusTreeNode parent;// 父级
		public int[] keywords;

		public abstract int fillArr(int[] r, int idx);
	}

	/**
	 * 这是 B+ 树中叶子节点的定义。
	 *
	 * B+ 树中的叶子节点跟内部结点是不一样的, 叶子节点存储的是值，而非区间。 这个定义里，每个叶子节点存储 3 个数据行的键值及地址信息。
	 *
	 * k 值是事先计算得到的，计算的依据是让所有信息的大小正好等于页的大小： PAGE_SIZE = k*4[keyw..
	 * 大小]+k*8[dataAd.. 大小]+8[prev 大小]+8[next 大小]
	 */
	public class BPlusTreeLeafNode extends Node {
		public int k = 4;
		public long[] dataAddress; // 数据地址

		public BPlusTreeLeafNode prev; // 这个结点在链表中的前驱结点
		public BPlusTreeLeafNode next; // 这个结点在链表中的后继结点

		public BPlusTreeLeafNode() {
			dataAddress = new long[k]; // 数据地址 PS这里就不写了
			keywords = new int[k]; // 数据的键值
		}

		public boolean remove(int k) {

			int idx = -1;
			for (int i = 0; i < size; i++) {
				if (k == keywords[i]) {
					idx = i;
					break;
				}
			}
			if (idx == -1) {
				// 不存在
				return false;
			}
			moveLeft(idx);
			size--;
			merge();

			return true;
		}

		// 合并或者借或者删除自己
		private void merge() {
			int idx = 0;
			// 找到自己在父级的索引
			for (; idx < parent.children.length; idx++) {
				if (parent.children[idx] == this) {
					break;
				}
			}

			// 当前节点没东西了
			if (size == 0) {
				parent.moveLeft(idx);
				parent.size--;
				parent.refresh();// 逐层向上刷新
				parent.merge();
				return;
			}

			// 判断是否需要合并 或者借节点
			if (size >= k / 2) {
				parent.refreshKey(idx);
				return;// 不需要
			}
			// 借或者取 然后要更新keyword
			if (idx > 0 && parent.children[idx - 1].size - 1 > k / 2) {

				// 前节点借
				int bIdx = idx - 1;
				BPlusTreeLeafNode b = (BPlusTreeLeafNode) parent.children[bIdx];
				moveRight(0);
				// 把兄弟节点的最后一个元素拿过来
				keywords[0] = b.keywords[--b.size];
				dataAddress[0] = b.dataAddress[b.size];
				size++;
				// 刷新key
				parent.refreshKey(bIdx);
			} else if (idx > 0 && parent.children[idx - 1].size + size < k) {

				// 前节点合并
				int bIdx = idx - 1;
				BPlusTreeLeafNode b = (BPlusTreeLeafNode) parent.children[bIdx];
				// 将当前节点的东西都转移到前节点 刷新key
				System.arraycopy(dataAddress, 0, b.dataAddress, b.size, size);
				System.arraycopy(keywords, 0, b.keywords, b.size, size);
				// 重新关联前后关系
				if (next != null) {
					next.prev = b;
				}
				b.next = next;
				//
				b.size += size;
				parent.moveLeft(idx);// 删除自己
				parent.size--;
				parent.refreshKey(bIdx);// 刷新key
				parent.merge();
			} else if (idx < parent.size - 1 && parent.children[idx + 1].size - 1 > k / 2) {

				// 后节点借
				int bIdx = idx + 1;
				BPlusTreeLeafNode b = (BPlusTreeLeafNode) parent.children[bIdx];
				keywords[size] = b.keywords[0];
				dataAddress[size++] = b.dataAddress[0];
				b.moveLeft(0);
				b.size--;
				parent.refreshKey(idx);// 刷新自己
			} else if (idx < parent.size - 1 && parent.children[idx + 1].size + size < k) {
				// 后节点合并
				int bIdx = idx + 1;
				BPlusTreeLeafNode b = (BPlusTreeLeafNode) parent.children[bIdx];
				System.arraycopy(b.dataAddress, 0, dataAddress, size, b.size);
				System.arraycopy(b.keywords, 0, keywords, size, b.size);
				size += b.size;
				// 重新关联前后关系
				if (b.next != null) {
					b.next.prev = this;
				}
				next = b.next;
				// 刷新
				parent.moveLeft(bIdx);
				parent.size--;
				parent.refreshKey(idx);
				parent.merge();
			} else {
				parent.refreshKey(idx);
			}

		}

		/**
		 * 指定IDX的左移(等同于删掉指定IDX)
		 */
		private void moveLeft(int idx) {
			// size - 1 - idx 为当前节点右边的元素数量（不含自己）
			System.arraycopy(keywords, idx + 1, keywords, idx, size - 1 - idx);
			System.arraycopy(dataAddress, idx + 1, dataAddress, idx, size - 1 - idx);
		}

		/**
		 * 指定IDX的右移(将IDX的位置让出来，方便插入)
		 */
		private void moveRight(int idx) {
			// size - idx 为当前节点以及当前节点右边的元素数量（含自己）
			System.arraycopy(keywords, idx, keywords, idx + 1, size - idx);
			System.arraycopy(dataAddress, idx, dataAddress, idx + 1, size - idx);
		}

		@Override
		public String toString() {
			return "{ \"leafSize\":" + size + ",\"leafKey\":" + printArr(keywords, size) + "}";
		}

		/**
		 * 测试用的方法 新增删除过程中进行验证 实际使用的时候 应该去掉此方法
		 */
		@SuppressWarnings("static-access")
		public void check() {
			for (int i = 0; i < size; i++) {
				if (keywords[i] != dataAddress[i]) {
					System.out.println("err1");
					System.out.println(h);
					System.exit(0);
				}
			}
			BPlusTreeNode p = parent;
			while (p != null) {
				for (int i = 0; i < p.size; i++) {
					Node c = p.children[i];
					try {
						if (p.keywords[i] != c.keywords[c.size - 1]) {
							System.out.println("err2");
							System.out.println(h);
							System.out.println("出现异常的指令数量:" + BPlusTree.this.c);
							System.out.println("异常过程->" + str);
							// test();
							System.exit(0);
						}
					} catch (Exception e) {
						e.printStackTrace();
						System.out.println("err3");
						System.out.println(h);
						System.out.println("出现异常的指令数量:" + BPlusTree.this.c);
						System.out.println("异常过程->" + str);
						System.exit(0);
					}

				}

				p = p.parent;
			}

		}

		public int exists(int k) {
			for (int i = 0; i < size; i++) {
				if (k == keywords[i]) {
					return i;
				}
			}
			return -1;
		}

		public boolean add(int k, long v) {
			int idx = exists(k);
			if (idx > -1) {// 已存在
				// 覆盖
				dataAddress[idx] = v;
				return false;
			}

			idx = 0;
			while (idx < size && k > keywords[idx]) {
				idx++;
			}

			// 更新节点
			// System.arraycopy(keywords, idx, keywords, idx + 1, size - idx);
			// System.arraycopy(dataAddress, idx, dataAddress, idx + 1, size -
			// idx);
			moveRight(idx);
			keywords[idx] = k;
			dataAddress[idx] = v;
			// 当前是 叶子节点的最后一个的时候 并且在值比原有的最大值更大的时候
			if (idx == size++) {
				// 向上更新当前节点
				if (parent != null) {
					idx = 0;
					// 找到自己在父级的索引
					for (; idx < parent.children.length; idx++) {
						if (parent.children[idx] == this) {
							break;
						}
					}
					parent.refreshKey(idx);
				}
			}

			// 不需要分裂
			if (size < this.k) {
				return true;
			}
			// 一边一半
			size = size / 2;
			// 分裂新节点
			BPlusTreeLeafNode node = new BPlusTreeLeafNode();
			// 复制属性

			node.size += this.k - size;
			System.arraycopy(keywords, size, node.keywords, 0, node.size);
			System.arraycopy(dataAddress, size, node.dataAddress, 0, node.size);
			// 关联
			if (this.next != null) {
				next.prev = node;
			}
			node.next = this.next;
			this.next = node;
			node.prev = this;

			node.parent = parent;
			// 父级判断
			parent.add(this, node);
			return true;
		}

		@Override
		public int fillArr(int[] r, int idx) {
			for (int i = 0; i < size; i++) {
				r[idx++] = keywords[i];
			}
			return idx;
		}

	}

	public static String printArr(int[] keywords, int s) {
		String r = "[";
		for (int i = 0; i < keywords.length && i < s;) {
			r += keywords[i++];
			if (i < keywords.length && i < s) {
				r += ",";
			}
		}
		r += "]";
		return r;
	}

	public static String printArr(Node[] keywords, int s) {
		String r = "[";
		for (int i = 0; i < keywords.length && i < s;) {
			r += keywords[i++];
			if (i < keywords.length && i < s) {
				r += ",";
			}
		}
		r += "]";
		return r;
	}

	/**
	 * 简易链表节点
	 */
	class SmallLinkedNode {

		int k;// 节点值

		SmallLinkedNode next;

		public SmallLinkedNode() {
		}

		public SmallLinkedNode(int k) {
			this.k = k;
		}

		// 添加一个新的链表节点 并返回该新节点
		public SmallLinkedNode setNext(int k) {
			this.next = new SmallLinkedNode(k);;
			return next;
		}
	}
}

A*算法

A*算法是对dijkstra的一种改进的寻路算法，利用启发函数替代路径，提高了效率，但是结果不一定是最好的。我这里写了2版，一版是二维数组来表示X，Y轴坐标的。另一版是邻接表的。

二维数组

package algorithm.senior.astar;

import java.util.ArrayList;
import java.util.List;
import java.util.function.Consumer;

import algorithm.senior.bitmap.BitMapTest.BitMap;
import algorithm.util.RandomUtil;

//a*算法
public class AStarArrayTest {
	public static void main(String[] args) {
		test();

	}

	private static void test() {
		// 随机demo
		int len = 21;// 边长
		int rate = 90;// 空白区域的估计占比 0~100
		BitMap[] m = randomMap(len, rate);
		aStar(m, RandomUtil.randomNum(len), RandomUtil.randomNum(len), RandomUtil.randomNum(len),
				RandomUtil.randomNum(len));

	}

	public static void aStar(BitMap[] m, int x1, int y1, int x2, int y2) {
		System.out.println("从(" + x1 + "," + y1 + ")去" + "(" + x2 + "," + y2 + ")");
		if (!m[x1].get(y1) || !m[x2].get(y2)) {
			System.err.println("起点或终点是不可达的");
			return;
		}
		System.out.println();
		// 初始化队列
		Vertex[][] vs = new Vertex[m.length][m.length];// 到每个点的距离
		PriorityQueue q = new PriorityQueue(m.length * m.length);// 优先级队列
		// 初始化
		for (int i = 0; i < vs.length; i++) {
			for (int j = 0; j < vs[i].length; j++) {
				vs[i][j] = new Vertex(Integer.MAX_VALUE, i, j);
			}
		}
		// 从根节点开始
		q.add(vs[x1][y1]);
		boolean flag = false;
		System.out.println("过程:");
		while (!q.isEmpty()) {
			// 每次取的都是最短距离的点
			// 所以 离当前起点越近的点就会越先处理
			// 所以当这个点就是目标节点的时候 就可以结束跳出了
			Vertex vt = q.poll();
			// 找到
			if (vt.x == x2 && vt.y == y2) {
				flag = true;
				break;
			}
			// 当前节点的所有相邻的
			List<Vertex> list = getVertex(vt, vs, m);
			//System.out.print("(" + vt.x + "," + vt.y +  "{"+vt.evaluation+"})->");
			System.out.println(vt+":");
			for (Vertex v : list) {
				//System.out.print("(" + v.x + "," + v.y + "{"+v.evaluation+"})");
				System.out.print(v);
			}
			System.out.println();
			for (int i = 0; i < list.size(); i++) {
				Vertex ve = list.get(i);
				// 计算起点从起始节点到这个边的目标节点的距离
				int dis = vt.dis + 1;
				int eval = dis + hManhattan(ve, vs[x2][y2]);// 曼哈顿距离
				if (eval < ve.evaluation) {
					// 判断之前到这个边的目标节点是否比从当前节点走更近
					// 更近就更新距离、队列、前驱节点
					ve.evaluation = eval;
					ve.prev = vt;// 前驱
					ve.dis = dis;
					q.updateOrAdd(ve);// 更新或者新增
				}

			}
		}
		if (flag) {
			
			print(m, vs, x1, y1, x2, y2);
			System.out.println("找到");
		} else {
			System.out.print("没找到");
		}
		System.out.println();
	}

	private static void print(BitMap[] m, Vertex[][] vs, int x1, int y1, int x2, int y2) {
		// 路径
		ArrayList<Vertex> path = new ArrayList<>();
		// 位图保存坐标信息
		BitMap[] way = new BitMap[m.length];
		Vertex curr = vs[x2][y2];
		System.out.println("路径回溯:");
		while (curr.x != x1 || curr.y != y1) {
			System.out.println(curr + "->");
			if (way[curr.x] == null) {
				way[curr.x] = new BitMap(vs.length);
			}
			way[curr.x].setTrue(curr.y);
			path.add(curr);
			curr = curr.prev;
		}
		System.out.println();
		// 起点
		path.add(curr);
		System.out.print("正序:");
		for (int i = path.size() - 1; i >= 0; i--) {
			Vertex v = path.get(i);
			System.out.print("(" + v.x + "," + v.y + ")->");
		}
		System.out.println();
		System.out.print("逆序:");
		path.stream().forEach(new Consumer<Vertex>() {
			@Override
			public void accept(Vertex v) {
				System.out.print("(" + v.x + "," + v.y + ")->");
			}
		});
		System.out.println();
		printMapWay(m, way, x1, y1, x2, y2);
	}

	// 获取周围8个顶点 如果没有则不返回
	private static ArrayList<Vertex> getVertex(Vertex vt, Vertex[][] m, BitMap[] bm) {
		int x = vt.x;
		int y = vt.y;
		int l = m.length;
		ArrayList<Vertex> al = new ArrayList<>();
		// x y轴的判断
		for (int i = x - 1; i <= x + 1; i++) {
			for (int j = y - 1; j <= y + 1; j++) {
				// 自身、X越界、Y越界的情况
				if ((i == x && y == j) || i < 0 || i >= l || j < 0 || j >= l) {
					continue;
				}
				// 可通过
				if (bm[i].get(j)) {
					// System.out.println("find:"+i+":"+j);
					al.add(m[i][j]);
				}
			}
		}

		return al;
	}

	public static BitMap[] randomMap(int s, int rate) {
		BitMap[] r = new BitMap[s];
		for (int i = 0; i < s; i++) {
			r[i] = new BitMap(s);
			for (int j = 0; j < s; j++) {
				if (RandomUtil.randomNum(101) < rate) {
					r[i].setTrue(j);
				}
			}
		}
		printMap(r);
		return r;
	}

	public static void printMapWay(BitMap[] m, BitMap[] way, int x1, int y1, int x2, int y2) {
		int s = m.length;
		System.out.println("路线地图（X代表障碍物,S表示起始点,●表示走过的路,E表示终点）");
		for (int i = s - 1; i >= 0; i--) {
			// System.out.print(i + " ");
			for (int j = 0; j < s; j++) {
				if (m[i].get(j)) {
					//
					if (i == x1 && j == y1) {
						System.out.print("S|");
					} else if (i == x2 && j == y2) {
						System.out.print("E|");
					} else if (way[i] != null && way[i].get(j)) {
						System.out.print("●|");
					} else {
						System.out.print(" |");
					}
				} else {
					System.out.print("X|");
				}
			}
			System.out.println();
		}
		// System.out.print(" ");
		// for (int i = 0; i < s; i++) {
		// System.out.print(i + " ");
		// }
		System.out.println();
	}

	public static void printMap(BitMap[] m) {
		int s = m.length;

		System.out.println("随机地图(X代表障碍物)");
		for (int i = s - 1; i >= 0; i--) {
			// System.out.print(i + " ");
			for (int j = 0; j < s; j++) {
				if (m[i].get(j)) {
					System.out.print(" |");
				} else {
					System.out.print("X|");
				}
			}
			System.out.println();
		}
		System.out.println();
	}

	public static int random(int max) {
		return ((int) (Math.random() * max));
	}

	public static int hManhattan(Vertex v1, Vertex v2) { // Vertex 表示顶点，后面有定义
		return Math.abs(v1.x - v2.x) + Math.abs(v1.y - v2.y);
	}

	// 因为 Java 提供的优先级队列，没有暴露更新数据的接口，所以我们需要重新实现一个
	public static class PriorityQueue { // 根据 vertex.dist 构建小顶堆
		private Vertex[] nodes;
		private int count;
		private int size = 0;

		public PriorityQueue(int v) {
			this.nodes = new Vertex[v + 1];
			this.count = v;
		}

		// 弹出首个
		public Vertex poll() {
			// 交换首尾节点
			swap(1, size--);
			// 从堆顶向下重新堆化
			buildDown(1);
			return nodes[size + 1];
		}

		// 新增
		public void add(Vertex v) {
			if (size == count) {// 满
				return;
			}
			// 放到最后一个节点去 然后和父节点进行比较
			nodes[++size] = v;
			buildUp(size);
		}

		// 交换
		private void swap(int i, int j) {
			Vertex temp = nodes[i];
			nodes[i] = nodes[j];
			nodes[j] = temp;
		}

		// 从下向上重新堆化
		private void buildUp(int idx) {
			while (idx / 2 > 0 && nodes[idx].evaluation < nodes[idx / 2].evaluation) {
				swap(idx, idx / 2);// 交换
				idx = idx / 2;
			}
		}

		// 从上向下重新堆化
		private void buildDown(int idx) {
			int m = idx;
			// left
			if (idx * 2 <= size && nodes[idx].evaluation > nodes[idx * 2].evaluation) {
				m = idx * 2;
			}
			// right
			if (idx * 2 + 1 <= size && nodes[m].evaluation > nodes[idx * 2 + 1].evaluation) {
				m = idx * 2 + 1;
			}
			// 是否有变化
			if (m != idx) {
				swap(idx, m);
				buildDown(m);
			}

		}

		private int findNode(Vertex v, int idx) {
			if (nodes[idx] == v) {
				return idx;
			}
			// 左节点
			if (idx * 2 <= size) {
				int f = findNode(v, idx * 2);
				if (f != -1) {
					return f;
				}
			}
			// right
			if (idx * 2 + 1 <= size) {
				int f = findNode(v, idx * 2 + 1);
				if (f != -1) {
					return f;
				}
			}
			return -1;
		}

		// 更新结点的值，并且从下往上堆化，重新符合堆的定义。时间复杂度 O(logn)。
		// 如果没有节点 就进行新增
		public void updateOrAdd(Vertex v) {
			// 首先找到节点的索引
			int idx = findNode(v, 1);
			if (idx == -1) {
				// 不存在
				add(v);// 不存在就进行新增
				return;
			}
			//////////////////////////////
			// 值如果变小 只需要向上重新堆化就可以了
			// 如果是值变大了 就只需要往下堆化即可
			// 也可以向上堆化和向下堆化都写，而实际的时候只会执行其中一个
			///////////////////////////////

			// 节点向下堆化
			buildDown(idx);
			// 从节点向上重新堆化
			buildUp(idx);

		}

		// 更新结点的值，并且从下往上堆化，重新符合堆的定义。时间复杂度 O(logn)。
		public void update(Vertex v) {
			// 首先找到节点的索引
			int idx = findNode(v, 1);
			if (idx == -1) {
				// 不存在
				return;
			}
			//////////////////////////////
			// 值如果变小 只需要向上重新堆化就可以了
			// 如果是值变大了 就只需要往下堆化即可
			// 也可以向上堆化和向下堆化都写，而实际的时候只会执行其中一个
			///////////////////////////////

			// 节点向下堆化
			buildDown(idx);
			// 从节点向上重新堆化
			buildUp(idx);

		}

		public boolean isEmpty() {
			return size < 1;
		}

	}

	// 下面这个类是为了 a* 实现用的
	public static class Vertex {
		public int x, y;// x y轴坐标
		public int dis; // 从起始顶点到这个顶点的距离 这里没有了权重(都是1) 可以无视这个
		// 到终点的估计距离
		// evaluation = dis + 当前顶点到终点的估计距离
		// 距离的计算就是启发函数(可以用曼哈顿距离或者欧几里得距离或者其他)
		// 曼哈顿距离计算较快 所以这里使用曼哈顿距离
		public int evaluation;
		public Vertex prev;

		public Vertex(int evaluation, int x, int y) {
			super();
			this.evaluation = evaluation;
			this.x = x;
			this.y = y;
		}

		@Override
		public String toString() {
			if(prev==null)
				return "(" + x + "," + y +  "{"+evaluation+"})";
			return "(" + x + "," + y +  "{"+evaluation+"},p=(" + prev.x + "," + prev.y + "))";
		}

	}

}

邻接表

package algorithm.senior.astar;

import java.util.LinkedList;

//a*算法
public class AStarTest {
	public static void main(String[] args) {
		// 随机demo
	}

	public static int random(int max) {
		return ((int) (Math.random() * max));
	}

	public static void aStar(Graph g, int s, int t) {
		LinkedList<Edge>[] adj = g.adj;// 所有边
		// 初始化队列
		PriorityQueue q = new PriorityQueue(g.v);
		int[] p = new int[g.v];// 距离当前节点最近的前驱节点
		Vertex[] vs = new Vertex[g.v];// 到每个点的距离
		for (int i = 0; i < vs.length; i++) {
			vs[i] = new Vertex(i, Integer.MAX_VALUE, Integer.MAX_VALUE);
		}
		vs[s].dis = 0;// 到起点零距离
		q.add(vs[s]);
		boolean flag = false;
		while (!q.isEmpty()) {
			// 每次取的都是最短距离的点
			// 所以 离当前起点越近的点就会越先处理
			// 所以当这个点就是目标节点的时候 就可以结束跳出了
			Vertex vt = q.poll();
			// 找到
			if (vt.id == t) {
				flag = true;
				break;
			}
			// 当前最短节点的所有边
			LinkedList<Edge> list = adj[vt.id];
			for (int i = 0; i < list.size(); i++) {
				Edge e = list.get(i);// 边
				// 计算起点从起始节点到这个边的目标节点的距离
				int distNew = vs[e.sid].dis + e.w;
				int eval = distNew + hManhattan(vs[e.tid], vs[t]);// 曼哈顿距离
				if (eval < vs[e.tid].evaluation) {
					// 判断之前到这个边的目标节点是否比从当前节点走更近
					// 更近就更新距离、队列、前驱节点
					vs[e.tid].dis = distNew;
					vs[e.tid].evaluation = eval;
					q.updateOrAdd(vs[e.tid]);// 更新或者新增
					p[e.tid] = vt.id;// 前驱
				}

			}
		}
		if (flag) {
			LinkedList<Integer> path = new LinkedList<Integer>();
			int idx = t;
			while (idx != s) {
				path.add(idx);
				idx = p[idx];

			}
			System.out.println("找到->");
			path.add(idx);
			for (int i = path.size() - 1; i >= 0; i--) {
				System.out.print(path.get(i) + ",");
			}
		} else {
			System.out.print("没找到");
		}
		System.out.println();
	}

	public static int hManhattan(Vertex v1, Vertex v2) { // Vertex 表示顶点，后面有定义
		return Math.abs(v1.x - v2.x) + Math.abs(v1.y - v2.y);
	}

	// 因为 Java 提供的优先级队列，没有暴露更新数据的接口，所以我们需要重新实现一个
	public static class PriorityQueue { // 根据 vertex.dist 构建小顶堆
		private Vertex[] nodes;
		private int count;
		private int size = 0;

		public PriorityQueue(int v) {
			this.nodes = new Vertex[v + 1];
			this.count = v;
		}

		// 弹出首个
		public Vertex poll() {
			// 交换首尾节点
			swap(1, size--);
			// 从堆顶向下重新堆化
			buildDown(1);
			return nodes[size + 1];
		}

		// 新增
		public void add(Vertex v) {
			if (size == count) {// 满
				return;
			}
			// 放到最后一个节点去 然后和父节点进行比较
			nodes[++size] = v;
			buildUp(size);
		}

		// 交换
		private void swap(int i, int j) {
			Vertex temp = nodes[i];
			nodes[i] = nodes[j];
			nodes[j] = temp;
		}

		// 从下向上重新堆化
		private void buildUp(int idx) {
			while (idx / 2 > 0 && nodes[idx].evaluation < nodes[idx / 2].evaluation) {
				swap(idx, idx / 2);// 交换
				idx = idx / 2;
			}
		}

		// 从上向下重新堆化
		private void buildDown(int idx) {
			int m = idx;
			// left
			if (idx * 2 <= size && nodes[idx].evaluation > nodes[idx * 2].evaluation) {
				m = idx * 2;
			}
			// right
			if (idx * 2 + 1 <= size && nodes[m].evaluation > nodes[idx * 2 + 1].evaluation) {
				m = idx * 2 + 1;
			}
			// 是否有变化
			if (m != idx) {
				swap(idx, m);
				buildDown(m);
			}

		}

		private int findNode(Vertex v, int idx) {
			if (nodes[idx] == v) {
				return idx;
			}
			// 左节点
			if (idx * 2 <= size) {
				int f = findNode(v, idx * 2);
				if (f != -1) {
					return f;
				}
			}
			// right
			if (idx * 2 + 1 <= size) {
				int f = findNode(v, idx * 2 + 1);
				if (f != -1) {
					return f;
				}
			}
			return -1;
		}

		// 更新结点的值，并且从下往上堆化，重新符合堆的定义。时间复杂度 O(logn)。
		// 如果没有节点 就进行新增
		public void updateOrAdd(Vertex v) {
			// 首先找到节点的索引
			int idx = findNode(v, 1);
			if (idx == -1) {
				// 不存在
				add(v);// 不存在就进行新增
				return;
			}
			//////////////////////////////
			// 值如果变小 只需要向上重新堆化就可以了
			// 如果是值变大了 就只需要往下堆化即可
			// 也可以向上堆化和向下堆化都写，而实际的时候只会执行其中一个
			///////////////////////////////

			// 节点向下堆化
			buildDown(idx);
			// 从节点向上重新堆化
			buildUp(idx);

		}

		// 更新结点的值，并且从下往上堆化，重新符合堆的定义。时间复杂度 O(logn)。
		public void update(Vertex v) {
			// 首先找到节点的索引
			int idx = findNode(v, 1);
			if (idx == -1) {
				// 不存在
				return;
			}
			//////////////////////////////
			// 值如果变小 只需要向上重新堆化就可以了
			// 如果是值变大了 就只需要往下堆化即可
			// 也可以向上堆化和向下堆化都写，而实际的时候只会执行其中一个
			///////////////////////////////

			// 节点向下堆化
			buildDown(idx);
			// 从节点向上重新堆化
			buildUp(idx);

		}

		public boolean isEmpty() {
			return size < 1;
		}

	}

	public static class Graph { // 有向有权图的邻接表表示
		private LinkedList<Edge> adj[]; // 邻接表
		private int v; // 顶点个数

		public Graph(int v) {
			this.v = v;
			this.adj = new LinkedList[v];
			for (int i = 0; i < v; ++i) {
				this.adj[i] = new LinkedList<>();
			}
		}

		public void addEdge(int s, int t, int w) { // 添加一条边
			this.adj[s].add(new Edge(s, t, w));
		}
	}

	public static class Edge {
		public int sid; // 边的起始顶点编号
		public int tid; // 边的终止顶点编号
		public int w; // 权重

		public Edge(int sid, int tid, int w) {
			this.sid = sid;
			this.tid = tid;
			this.w = w;
		}
	}

	// 下面这个类是为了 a* 实现用的
	public static class Vertex {
		public int id; // 顶点编号 ID
		public int dis; // 从起始顶点到这个顶点的距离
		public int x, y;// x y轴坐标
		// 到终点的估计距离
		// evaluation = dis + 当前顶点到终点的估计距离
		// 距离的计算就是启发函数(可以用曼哈顿距离或者欧几里得距离或者其他)
		// 曼哈顿距离计算较快 所以这里使用曼哈顿距离
		public int evaluation;

		public Vertex(int id, int dist, int evaluation) {
			this.id = id;
			this.dis = dist;
			this.evaluation = evaluation;
		}
	}

}

Review 英文文章

https://spring.io/projects/spring-cloud

spring cloud 的介绍

Tip 技巧

极客时间的专栏《数据结构与算法之美》

本周学习了该专栏中的48/49篇

学习了B+树，

这是一种树结构的数据，利用节点的分裂合并来达到自动平衡的效果。

查找和插入的性能都是logn，除此之外最大的优势是适合区间查找，以及是个多叉树的结构，适合储存进磁盘当索引使用。

Astar算法，Astar算法是对dijkstra的一种改进的寻路算法，提高了效率，但是结果不一定是最好的。

Share 分享

https://blog.csdn.net/ityouknow/article/details/96533522

spring boot的使用技巧