1.树的定义

树可以用如下的方式递归的进行定义

树是n(n>=0)个结点的有限集。它

（1）或者是一棵空树（n=0），空树中不包含任何结点

（2）或者是一棵非空树（n>0），此时有且仅有一个特定的称为 根（root） 的结点；当n>1时，其余结点可以分为m(m>0)个互不相交的有限集T1,T1,…,Tm，其中每一个本身又是一棵树，并且称为根的 子树（sub tree）

如上的定义形式并不直观，如下有一些树的示例。

场景

数据表结构如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

CREATE TABLE `doc_transfer` (
  `id` bigint(20) unsigned NOT NULL AUTO_INCREMENT,
  `source_type` int(11) NOT NULL,
  `source_id` varchar(128) COLLATE utf8mb4_unicode_ci NOT NULL DEFAULT '',
  `owner_type` int(11) NOT NULL,
  `owner_id` bigint(20) NOT NULL,
  `doc_id` bigint(20) NOT NULL,
  `cts` datetime NOT NULL,
  `uts` datetime NOT NULL,
  PRIMARY KEY (`id`), 
  UNIQUE KEY `source` (`source_type`,`source_id`)) 
ENGINE=InnoDB 
AUTO_INCREMENT=107
DEFAULT CHARSET=utf8mb4 
COLLATE=utf8mb4_unicode_ci;

什么是散列表

散列表利用是数组支持时间复杂度是 O(1) 按照下标随机访问数据的特性。通过散列函数把元素的键值映射为下标，将数据存储在数组中对应下标的位置的数据结构。当我们按照键值查询元素时，我们用同样的散列函数，将键值转化数组下标，从对应的数组下标的位置取数据。

1.概述

索引是存储引擎用于快速找到记录的一种数据结构。在数据量大的时候，索引对性能的影响是巨大的，索引优化是对查询性能优化的最有效的手段，能轻易的将查询性能提高几个数量级。

1.常用的分布式ID生成方法

在应用程序中，经常需要全局唯一的ID用作标识，可能是需要入库数据的主键，也可能是发出的消息的唯一性标识等。这种ID一般有一些一些要求：

• 长整型。
• 趋势自增。
• 全局唯一。
  阅读全文 »

1.B树

1.1 B树的特点

B树也称B-树,它是一颗多路平衡查找树。m阶B树有如下特性：

• 每个节点最多有m-1个关键字。m个子节点。
• 根节点最少可以只有1个关键字。非根节点至少有Ceil(m/2)个关键字。
• 每个节点中的关键字都按照从小到大的顺序排列，每个关键字的左子树中的所有关键字都小于它，而右子树中的所有关键字都大于它。
• 所有叶子节点都位于同一层（根节点到每个叶子节点的长度都相同）。
• 所有节点在包含关键字的同时包含关键字对应的数据（即key&value都包含）。
  阅读全文 »

1.事实

客观世界中，可以被证实或者证伪的东西。

提到分布式系统就会提到CAP理论，这里从个人角度简要的阐述一下对CAP的理解。

对称加密

加密解密使用同一个秘钥，加密速度快。常见的对称加密算法有:

• DES
• 3DES
• AES
• RC4
• RC5
• Blowfish

AES由于得到了cpu 指令集级别的支持（AES指令集），加密速度快。优先考虑使用。

1.总览

Unsafe是位于sun.misc包下的一个类，主要提供一些用于执行低级别、不安全操作的方法，如直接访问系统内存资源、自主管理内存资源等，这些方法在提升Java运行效率、增强Java语言底层资源操作能力方面起到了很大的作用。