高数

阶乘

阶乘是基斯顿·卡曼(Christian Kramp,1760~1826)于 1808 年发明的运算符号。
一个正整数的阶乘(factorial)是所有小于及等于该数的正整数的积,并且0的阶乘为1。自然数n的阶乘写作n!。1808年,基斯顿·卡曼引进这个表示法。
亦即n!=1×2×3×…×n。阶乘亦可以递归方式定义:0!=1,n!=(n-1)!×n。阶乘没有封闭的通项公式。

组合

组合(combination),数学的重要概念之一。从n个不同元素中每次取出m个不同元素(0≤m≤n),不管其顺序合成一组,称为从n个元素中不重复地选取m个元素的一个组合。所有这样的组合的总数称为组合数。

排列

排列可分选排列与全排列两种,在从n个不同元素取出m个不同元素的排列种,当m小于n时,这个排列称为选排列;当m=n时,这个排列称为全排列。n个元素的全排列的个数记为Pn。
Pn=n!。

同济高等数学第六版上册习题全解指南.
https://pan.baidu.com/share/link?uk=2317362003&shareid=3026054346
人教版高中数学电子课本全套pdf
https://zhidao.baidu.com/question/1888471680276922628.html

计算公式

阶加:1+2+3+…+n = n(n+1)/2
阶乘:1×2×3×…×n = n! = (n-1)! * n

数学符号

定义符号“[]”为取整符号,即[x]表示一个小于或等于x的最大整数,读作高斯x。
向上取整,取比自己大的最小整数, 运算称为 Ceiling,用数学符号 ⌈⌉ (上有起止,开口向下)表示。
向下取整,取比自己小的最大整数,运算称为 Floor,用数学符号 ⌊⌋ (下有起止,开口向上)表示。
对整数向上向下取整,结果都是整数自己。

JS函数:

1. 向上取整,有小数就整数部分加1
Math.ceil(5/2)  //3
2. 四舍五入.
Math.round(5/2)  //3
3. 向下取整
Math.floor(5/2) //2

计算器log以2为底,用换底公式:log(2)x=(lnx)/(ln2)。

|集合A| 表示集合A的点的数量。

http://www.fhdq.net/sx/12.html

Spring boot 项目容器化

1.在pom.xml中增加使用docker-maven-plugin,Spring Boot Maven plugin 提供了很多方便的功能,包括:
收集的类路径上所有 jar 文件,并构建成一个单一的、可运行的jar。
搜索 public static void main() 方法来标记为可运行的类。

<properties>
    <docker.image.prefix>wwk</docker.image.prefix>
</properties>
<build> 
<plugins> 
<plugin> 
<groupId>com.spotify</groupId> 
<artifactId>docker-maven-plugin</artifactId> 
<configuration> 
<imageName>${docker.image.prefix}/${project.artifactId}</imageName> 
<dockerDirectory>src/main/docker</dockerDirectory> 
<resources> 
<resource> 
<targetPath>/</targetPath> 
<directory>${project.build.directory}</directory> 
<include>${project.build.finalName}.jar</include> 
</resource> 
</resources> 
</configuration> 
</plugin> 
</plugins> 
</build>

imageName指定镜像的名字。
dockerDirectory指定 Dockerfile文件 的位置。
resources是指那些需要和 Dockerfile 放在一起,在构建镜像时使用的文件。

构建镜像有两种方式,第一种是将构建信息指定到 POM 中,第二种是使用 Dockerfile 配置构建信息。
2.编写Dockerfile
Docker 使用 Dockerfile 文件格式来指定 image 层。
创建文件 src/main/docker/Dockerfile:

FROM frolvlad/alpine-oraclejdk8:slim
VOLUME /tmp
ADD test-docker-1.0.0.jar app.jar
ENTRYPOINT ["java","-Djava.security.egd=file:/dev/./urandom","-jar","/app.jar"]

3.执行构建和运行镜像

mvn package docker:build
docker run -p 8080:8080 -t wwk/test-docker

[INFO] Copying /Users/hycx/i_workspace/test/test-docker/target/test-docker-0.0.1-SNAPSHOT.jar -> /Users/hycx/i_workspace/test/test-docker/target/docker/test-docker-0.0.1-SNAPSHOT.jar
[INFO] Copying src/main/docker/Dockerfile -> /Users/hycx/i_workspace/test/test-docker/target/docker/Dockerfile
[INFO] Building image wwk/test-docker

4.
手动上传Dockerfile和jar文件到服务器,到同目录下,运行下面的命令,生成镜像。

docker build -t wwk/test-docker .
docker images

用 Docker 构建、运行、发布来一个 Spring Boot 应用
https://blog.csdn.net/kkkloveyou/article/details/50942275

Alpine Linux

frolvlad/alpine-oraclejdk8:slim 镜像的基础镜像是 Alpine Linux 3.7。
Alpine Linux 是一个社区开发的面向安全应用的轻量级 Linux 发行版。Alpine采用了musl libc和busybox以减小系统的体积和运行时资源消耗,在保持瘦身的同时,Alpine Linux还提供了自己的包管理工具apk,可以在其网站上查询,或者直接通过apk命令查询和安装。
Alpine Linux作为基础镜像只有5MB。

Spring boot 与 docker

Springboot服务本质上是一个java服务,它也可以同时在jar中打包一个Web服务器例如tomcat。java服务运行所依赖的就是java虚拟机,java虚拟机在大多数操作系统上都会安装。而spring boot服务可以打包为一个可执行的jar,可以很简单的运行管理。这样,一般地在已经安装了java运行环境的服务器上,把spring boot服务运行于docker内的必要性就不大了。

二叉树

第i(i>=1)层上结点数最大值:2i-1。即1、2、4、8、16…。
深度为i的树的结点数最大值,或从第i(i>=1)到1层所有结点数最大值:2i-1。即1、3、7、15、31。这称为满二叉树。满二叉树的结点数为2k-1,只有度为0和2的结点,并且叶结点都处在最下层。
结点总数n=n2+n1+n0,度为0的结点数n0=n2+1,即叶结点数比双分支的结点数多1个。

完全二叉树中度为1的结点数是0或1。
完全二叉树,n个结点,深度=⌊log2n⌋+1。
完全二叉树,若深度k>1,则叶子结点数>=2k-2
深度为k的完全二叉树,结点数最少是2k-1-1+1。
深度为k的二叉树,结点数最多为2k-1,最少为k。
深度为k的二叉树,若只有度为0、2的结点,结点数最少为2k-1。
第i个结点的父结点编号为⌊i/2⌋,左孩子编号为2*i,右孩子编号为2*i+1。
n个结点的二叉树中,有2n个指针域,n-1个指针域不为空,n+1个指针域为空,结果发现2n没有被平分,而是多出了一个空指针域是因为根结点没有被指向。

结点的度:结点的子树的数目。
树的度:树中最大的结点度。
树的高度:也叫深度,即从1开始的最大层次数。
树的出度:树中结点度为D(D>=0)的结点的个数与D的乘积。
树的结点数=各个度(0到树的度)的结点的个数之和=各个结点的度之和再加一。

存储

完全二叉树的顺序存储结构中,编号为i的结点的层次为⌈log2(i+1)⌉ 。

二叉树的链式存储结构中,三叉链表比二叉链表的结点中多了一个parent指针域。

遍历

先序序列的第一个结点是根结点,后序序列的最后一个结点是根结点,中序序列中由根结点将序列分为为两部分。

先序序列和中序序列相反,则二叉树每个结点只有左子树,左单极树。
先序序列和中序序列相同,则二叉树每个结点只有右子树。
先序序列和后序序列相反,则二叉树高度和结点数相同即可。
先序序列和后序序列相同,则二叉树只有一个根结点。
从一个遍历序列推导出不同形状的二叉树,首先宽二叉树,然后是多种每层单节点二叉树。

中序序列中前后结点在二叉树中的关系是,前面的结点在后面的结点的左边,左边是指左子或其所在分支的父。
交换所有分支左右子树的位置,利用前序遍历方法最合适。
一棵二叉树的前序序列和中序序列,或后序和中序序列可唯一确定这棵二叉树。在先序中第一个字符是根结点,而在后序中最后一个字符是根结点。在中序中,根结点前后分别是其左右子树。按照这个思想递归可推导出二叉树。
方法一:以中序为主线,在前序中找中序的根:
1.在中序中,由树的根分左序L,右序R。在先序中找到排在根后面的第一个L中的值,即为根的左结点。同样地,在先序中找到排在根后面的第一个R中的值,即为根的右结点。在中序中标记根值为墙表示它是已处理完毕的界线,在树中对字符画圈也表示它已处理完毕。
2.再把左右两个结点分别视为根,依次进行步骤1。
当是在后序序列中辅助查找时,方向是从后向前。

遍历实现

1.二叉链表上遍历的递归实现。还可以利用递归遍历求得二叉树的高度为较高的子树的高度加1。
2.二叉树的层次遍历可以借助队列来实现。将根结点入队列,从队列中出一个结点,将该结点的左右孩子结点入队列。如此出入直至队列为空。则入队列或出队列的顺序即为层次遍历的序列。
3.二叉树顺序存储或链式存储上的非递归实现可以借助栈来实现。

算法:输出二叉树各结点的值

//中序遍历
void printtree (BiTree BT)
{
  BiTnode* p=BT;
  InitStruct(s); //构造一个数组结构s
  s.top=0;
  
  while (p || s.top!=0)
  { 
    //把p、左子、左子的左子...,存入eles。
    while (p)
    { 
      s.eles[s.top++]=p;
      p=p->lchild ;
    }
    
    if (s.top>0)
    { 
      //输出eles中最后一个元素。
      p=s.eles[s.top--];
      cout < < p->data;//int pos=s.top,输出的元素将不在eles中继续保存。
      //遍历p的右子树
      p=p->rchild; //在下一次进入循环时,eles[pos]会被替换为p,即原p的右子结点。
    }
  }
}

树和二叉树的转换

树转二叉树:
1.将所有兄弟连接起来;
2.保留兄弟中的第一个结点与父结点的连接,断开其它的父连接;
3.结果即是使这条兄弟链变成以兄长为根的子树,子树外部左排列、子树内部右排列;
转换后得到的二叉树的根结点的右子树总是空的。

森林转二叉树:
1.将森林中的每棵树转为二叉树;
2.将每棵树对应的二叉树的根作为兄弟结点连接起来;
3.同样遵循子树外部左排列、子树内部右排列的规则;
森林中有m个非终端结点,则其对应的二叉树中有m+1个右指针域为空的结点。右指针为空,即没有右孩子。因为每个非终端结点转换成二叉树后都对应(本身是,或者它的右孩子…是)一个无右孩子的结点,另外最后一棵树的根结点转换后也没有右孩子。
转换后得到的二叉树的根结点和其左子对对应森林中的第一棵树,右子树对应森林中的所有其它树。

二叉树转森林:
1.将根结点与其右子树上所有连线断开,得到多棵无右子树的二叉树。
2.把每个二叉树中的所有右支中的各结点依次断开连接并连接到支的父结点;

树的遍历

树的先序遍历,与其对应的二叉树的先序遍历,结果相同。
树的中序遍历,与其对应的二叉树的中序遍历,结果相同。

哈夫曼(Huffman)树

树的应用之一是可以描述分类过程,按标准将数据划分为不同的种类。

判定树:描述分类过程的二叉树。分类问题中的因素有总数N,某个类别的属性有名称、条件、占比(权重)。二叉树中分叉结点表示判断条件,叶子结点表示值。判断树中的问题在于,同一个分类问题有不同的分类算法,会产生不同的判定树。它们从表面上看有纵深形状或水平形状,那么它们的总加权遍历查找的计算量也不同。则判定树中要研究的课题是要使平均比较次数计算量最小,使权重大的类别的比较次数尽量少。

哈夫曼算法和哈夫曼树,是从序列生成树的过程:
1.给定一组类别,{p1,p2,…,pk},其初始对应为单根树的森林{T1,T2…Tk}。
2.从森林中选两个根结点权(即占比)最小的树合并,它们分别为新树的左右子树,整齐起见可以按左小右大排列,新树的根结点权为左右子结点权之和。
3.直到森林中只剩一棵最小带权路径长度的二叉树,即哈夫曼树。
哈夫曼树也是满二叉树,其中共有2n0-1个结点,n0个叶结点是初始森林中的结点数。
WPL(Weight Path Length Of Node 带权路径长度)= 权与比较次数的乘积之和。

哈夫曼树的树形不一定唯一,但其WPL值最小且相等
哈夫曼字符编码不一定唯一,但总码长最短
哈夫曼树没有严格要求区别左右子树权重次序

哈夫曼编码:
在通信领域,希望字符在传输中总编码长度最短。
给出所有不同的字符,根据其出现次数比重构造哈夫曼树,然后将每个结点的左分支路径标记为0,右分支路径标记为1,每个叶结点都有一个从根结点开始的唯一的0、1序列,这个序列即是这个字符的编码,即哈夫曼编码。

下端物联网架构

物联网(Internet Of Things)

GPRS模块与云端通信,
GPRS模块通过串口与zigbee模块通信,
zigbee模块通过有线与传感器模块通信,或者zigbee主模块与多个zigbee从模块通信,zigbee从模块再通过有线与传感器通信。

zigbee具有自组网功能,从模块之间也可以通信。

2538 zigbee。
2540 蓝牙

485接口

物联网云平台:
百度云开工
机智云
选型的因素包括:有的系统只能在局域网内部使用。

机智云等使用缺点:
费用,
数据不能自己保存,第三方存储也不安全,
不能灵活定制。

Qsc厂家的数字音频处理器
给录播编码器配置信号源;

继承SchedulingConfigurer类并重写其方法,实现并行任务

Spring Boot Starter

传统Maven项目中通常将一些层、组件拆分为模块来管理,以便相互依赖复用。在Spring Boot项目中我们则可以创建自定义Spring Boot Starter来达成该目的。

配置pom

自定义starter并且通过spring-boot-autoconfigure完成自动化配置。
在pom.xml中配置对spring-boot-autoconfigure的依赖,如果继承了spring-boot-starter-parent,则可以不配置。

<dependency>
 <groupId>org.springframework.boot</groupId>
 <artifactId>spring-boot-autoconfigure</artifactId>
 </dependency>

配置映射参数实体

Spring Boot提供了一个注解@ConfigurationProperties,该注解可以完成将application.properties配置文件内的有规则的配置参数映射到实体内的field内,实体需要提供setter方法。

import org.springframework.boot.context.properties.ConfigurationProperties;
@ConfigurationProperties(prefix = "前缀")
public class HelloProperties
{
    //消息内容
    private String msg = "default message";
}

编写业务类

实现自动化配置

自动化配置提供实体bean的验证以及初始化。

import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.boot.autoconfigure.condition.ConditionalOnClass;
import org.springframework.boot.autoconfigure.condition.ConditionalOnMissingBean;
import org.springframework.boot.autoconfigure.condition.ConditionalOnProperty;
import org.springframework.boot.context.properties.EnableConfigurationProperties;
import org.springframework.context.annotation.Bean;
import org.springframework.context.annotation.Configuration;

@Configuration//开启配置
@EnableConfigurationProperties(HelloProperties.class)//开启使用映射实体对象
//初始化该配置类的多个条件注解
@ConditionalOnClass(HelloService.class)
@ConditionalOnProperty(
                prefix = "hello",//存在配置前缀hello
                value = "enabled",//开启
                matchIfMissing = true//缺失检查
)
public class HelloAutoConfiguration
{
    @Autowired
    private HelloProperties helloProperties;

    @Bean
    @ConditionalOnMissingBean(HelloService.class)
    public HelloService helloService()
    {
        HelloService helloService = new HelloService();
        helloService.setMsg(helloProperties.getMsg());//设置消息内容

        return helloService;
    }
}

指明自动化装配位置

在注解@SpringBootApplication中已经存在一个开启自动化配置的注解@EnableAutoConfiguration来完成自动化配置。@EnableAutoConfiguration内部使用了EnableAutoConfigurationImportSelector,继而使用了SpringFactoriesLoader.loadFactoryNames方法进行扫描具有META-INF/spring.factories文件的jar包。

我们在src/main/resource目录下创建META-INF目录,新建文件spring.factories,写入如下内容:

#配置自定义Starter的自动化配置,多个值可用逗号分隔。
org.springframework.boot.autoconfigure.EnableAutoConfiguration=com.xxx.HelloAutoConfiguration

@Conditional条件判断注解

Spring 4.X 新加入了@Conditional注解,控制某些configuration是否生效。除了自己自定义Condition,Spring还提供了很多ConditionalOn注解。这些注解里的条件可以是多个,可以赋默认值,也可以标注在类上。如果标注在类上,则对类里的所有@Bean方法都生效。

@ConditionalOnProperty(value = {"abc.property"}, matchIfMissing = false) #其name属性用来从application.properties中读取某个属性值,如果该值为空,则返回false。如果值不为空,则将该值与havingValue属性指定的值进行比较返回true或false。

开发中热部署

LiveReload Server,spring-boot-devtools

排序思想

直接插入排序

将后面的无序区中的元素挨个向前面的有序区中插入。
1.将顺序表中R[0]用作哨兵,按索引i=2…n的次序,将R[i]向有序区R[1…i-1]中执行插入操作。
2.插入操作可采取在有序区中从后向前的查找比较和移动的方法。
3.此操作中比较的次数与原序列的排列状态有关:
当原序列为正序时,在插入操作中插入位置为尾部即只需要比较一次,排序中比较的总次数为n-1,效率很高;
当原序列为反序时,插入位置为头部则需要和有序序列中的每个元素比较一次,效率很低。

时间复杂度:正序时O(n),反序时 O(n²),平均时间复杂度 O(n²)
空间复杂度:O(1),就地排序
直接插入排序是稳定的。

希尔排序(分组插入排序)

1.把序列分为d个组,分组方法为所有距离为d的元素划到一个组内。
2.各组内进行直接插入排序。
3.按照避免增量序列中的值互为倍数,及最后一个增量必须为1的原则,设定增量序列d。

希尔排序是不稳定的。

冒泡(交换)排序

1.从下面无序区的最底部元素开始向上两两比较,最小者交换到无序区的最顶部,它同时也处了在有序区的最底部。
2.当某一趟扫描中的两两比较未出现交换,则说明无序区已全部有序,排序结束。
在n-1趟起泡中,总的比较次数=(n-1)+(n-2)+…+1=(n-1)n/2。
新教材中是值大的从序列左边交换到最右边,右边为有序区。

时间复杂度:正序时O(n),反序时 O(n²),平均时间复杂度 O(n²)
空间复杂度:属于就地排序
冒泡排序是稳定的。性能低于直接插入排序。

(两端)快速(交换)排序(基准分冶)

1.确定基准
在区间R中可随机选择一个元素作为基准,和R[0]交换位置,则R[0]变为基准,通常直接取R[0]作为基准。
2.对比划分
以R[0]作为基准做一趟划分操作:从区间右端和左端向中间依次交替与基准比较大,根据小在左侧、大在右侧的规则与基准交换位置,最终生成比基准值小和大的左右两个无序的子区间。在一趟划分过程中区间元素逐渐变少,不包括已比较过的元素,左右交替要在成功交换后。
或者是把基准存放到一个临时变量中,在交换位置时是右左两端的当前值腾挪。
3.递归
对每个子区间递归定基准-划分过程。

划分操作结果中有一个子区间为空,及两个子区间都不为空,这两种情况比较,前者整体排序中做的比较次数更多。

时间复杂度:最好 O(nlgn),对有序序列最坏 O(n²),平均 O(nlgn)
空间复杂度:O(lgn)
快速排序是不稳定的。

直接选择排序

1.从后面的无序区中选择最小的元素,与无序区头部元素交换,则有序区末尾增加一个元素,无序区头部减少一个元素。
2.对新的有序区和无序区执行上一步操作。
对链表结构的数据做直接选择排序,可以只交换结点的数据,而不移动结点。
时间复杂度:O(n²),其键值比较的次数与初始序列的排列顺序无关。
空间复杂度:O(1),就地排序
直接选择排序是不稳定的,不稳定的原因在于步骤中的元素交换。

插入排序是先在指定位置取元素,然后再找合适的位置插入,重心在第二步的插入。
选择排序是先找最小的元素,然后交换到指定位置,重心在第一步的选择。

堆排序(树形选择排序)

相对于直接选择排序,堆排序是保存利用前n-1次比较所得的信息,来减少各次选择中比较的次数。
大根堆的排序结果为升序列。
首先定义调整堆(筛选):判断调整根子树,将根与两个孩子中较大者(大根堆)交换,继而判断调整有变动的子子树。
1.从序列建二叉树
将初始关键字序列转换为完全二叉树结构。
2.构造堆
在树中从下往上依次对位置编号为⌊n/2⌋…1为根的子树做调整堆操作。结果构造出堆,但并不有序。
3.将堆根元素交换到无序区尾部,即有序区首部。
令i为本次调整的序号,将堆顶元素R[1]和最后一个元素R[n-i+1]交换,则新的无序区变为R[1…n-i],有序区为R[n-i+1,n]。即输出堆顶元素,并且把最后一个元素换到堆顶。
4.判断调整重建堆
同步骤2。
5.对新的无序区重复3、4步骤共n-1次。

时间复杂度:平均和最坏都是 O(nlgn)
空间复杂度:O(1),就地排序
堆排序是不稳定的。

(两两)归并排序(二路归并排序)

1.将区间内的元素两两做二路归并。
2.将上一步形成的各个有序组两两做二路归并。
3.直至全部元素进入同一个有序组。
4.二路归并需要同等的辅助空间。

时间复杂度:O(nlgn)
空间复杂度:O(n),
归并排序是稳定的。

以上基于关键字比较的排序时间下限是O(nlgn),而分配排序无须比较关键字,通过分配和收集过来实现排序,它们的时间复杂度可以下破到线性阶O(n)。

箱排序(桶排序)

分配排序不基于关键字比较,而是通过分配和收集过程实现排序。时间复杂度可达线性阶。
第一种箱排序是设置箱子个数和关键字的种类的个数相同;
第二种桶排序是关键字映射到某个桶中,桶中的所有元素再单独做关键字比较排序

基数排序

基数排序要求分析关键字的结构,分为多关键字和单关键字,每个关键字又由多个位组成。
单关键字的每位即每个分量可能取值个数称为基数,
基数排序是按基数的个数次数从低位到高位对序列元素进行箱排序,每箱排序的结果作为下一趟排序的输入。

基数排序是稳定的。

构建用户管理微服务

处理密码重置和电子邮件确认等特权操作,要使用一次性随机令牌。

译见|构建用户管理微服务(一):定义领域模型和 REST API

安全设计技术栈(非功能性需求):
1.当用户登录时,将为他们生成一个 JWT 令牌,有效期是 24 小时。在后续请求中包含此令牌,用户可以执行需要身份验证的操作
2.密码重置令牌有效期为 10 分钟,电子邮件地址确认令牌为一天
3.密码用加密算法(Bcrypt)加密,并且每用户加盐

在领域驱动设计DDD中,先设计领域模型。

值对象
当设计领域模型,值对象提供了一种方便的方式来描述携带有一定的信息片段属性的集合。 AddressData,AuditData,ContactData 和 Password 因此可以认为是值对象。

查找思想

查找表的逻辑结构是集合。
静态查找表:只进行查找、读取元素的操作的查找表。我们不关心查找表的创建。
动态查找表:在查找前,我们要先根据原有集合创建这个查找表,并且在创建过程中需要查找,当查找不到元素时插入。

查找长度即是比较次数,平均查找长度ASL,是每个元素查找需要的比较次数*其查找概率,之和。每个元素查找概率相等即1/n。

线性表查找

1.顺序查找,ASL=(1+…+n)/n=(n(n+1)/2)/n=(n+1)/2。
平均时间复杂度 O(n)。
2.二分查找,也称折半查找,要求线性表是按关键字有序顺序表,只适用于静态查找表。
中间点位置=⌊(low+high)/2⌋,在和中间点位置值比较后,得出的左右两段都不再包含此中间点位置。
二分查找过程用二叉树来描述,称为描述二分查找的判定树,或比较树。
ASL=((n+1)/n)*lg(n+1)-1≈lg(n+1)-1。
树深度=⌈lg(n+1)⌉。
平均时间复杂度 O(lgn)。
3.分块查找,又称索引顺序查找,性能介于顺序和二分查找之间。安要求线性表分块有序。
它的索引表是由各块中的最大关键字及块起始位置组成的有序表。
先查找索引表,确定块,再在块内顺序查找。

树表之二叉排序树

二叉排序树,又称二叉查找树。中序遍历一棵二叉排序树可得到键值的升序序列。ASL介于O(lgn)和O(n)。
从键值序列生成二叉排序树:挨个把序列中的元素接入树中的左小右大的适当位置,每次增加的新结点都是树上的新的叶子结点。
运算:插入、生成、删除、查找。
平衡二叉树是指任一结点的左右子树的高度大致相同。
同一些关键字的不同序列,可能会得到相同的二叉排序树。这些序列的基本特征是开头字符相同,然后接着是全部右枝中的点或全部左枝中的点。

B-树

读作B树,即Balance Tree,多路平衡查找树。度为m的B树称为m阶B树。度数大则高度小,较大的度数使结点中的关键字较多,相比减小了磁盘访问次数。
一般地,文件中查找性能,受到的磁盘IO的次数的影响,远大于内存中比较的次数的影响。B树用于对较大的,存放在外部存储器上的文件内查找,是一种尽可能降低磁盘IO次数的文件组织方式。Mysql的数据索引存储即是基于Hash表或者B+树。
非根结点关键字数j:⌈m/2⌉-1<=j<m-1。

https://www.sohu.com/a/154640931_478315

散列(Hash)技术

和排序类似,要突破lgn的下界,就不能只依赖比较。
将结点按关键字的散列地址,存储到散列表中的过程,称为散列。
散列函数的作用是压缩待处理的下标范围|U|到m=O(|K|),即|K|的线性阶数量级,|K|<= m <|U|,所以从所有情况来看,冲突总会出现。
散列函数的标准是简单和均匀。有平方取中法、除余法、相乘取整法、随机数法。
处理冲突的方法:开放定址法(线性探查法、二次探查法、双重散列法)、拉链法。
地址单元为空的地址称为开放地址。
开放定址是当冲突发生时,用某种探查法在散列表中找到一个地址来放置这个冲突的结点。
散列表上的查找:
1.在散列表中查找散列地址h(K),若其单元为空,则查找失败。
2.比较其单元和K值是否相等,若相等则查找成功。
3.按冲突处理方法计算下一个散列地址h(K)。
堆积:是非同义词之间对一个散列地址的争夺现象,我理解为二次冲突、后继冲突,即解决冲突而给出的地址仍然已被占用了。