Go（又称Golang）是Google开发的一种静态强类型、编译型、并发型，并具有垃圾回收功能的开源编程语言。

一、Hello World

Golang源文件的扩展是.go，这些文件名均由小写字母组成，如hello.go。

一般情况，我们可以把整个数据结构存储到计算机的主存中；可如果数据更多装不下主存，那么意味着必须把数据结构放到磁盘上。 此时“大O模型”不再适用，因为大O分析假设所有操作耗时都是相同的，所以涉及到磁盘I/O就不再适用了。与内存相比，磁盘必须花成倍的时间来存取一个数据元素，这是因为磁盘的机械部件读写数据的速度远远赶不上纯电子媒体的内存。

【CPU】 <---> 【内存】 <--I/O--> 【磁盘】

当在大量数据存储中，查询时我们不能一下子将所有数据加载到内存中，只能逐一加载磁盘页，每个磁盘页对应树的节点。造成大量磁盘I/O操作（最坏情况下为树的高度）。 平衡二叉树由于树深度过大而造成磁盘I/O读写过于频繁，进而导致效率低下。 为了减少磁盘I/O操作的次数，就你必须降低树的深度，将“瘦高”的树变得“矮胖”。 所以，就引入了B 树。B 树利用多个分支（称为子树）的节点，减少获取记录时所经历的节点数，从而达到节省存取时间的目的。

1. B 树（B Tree）

B 树（B-Tree），是一种平衡的多路查找树，主要面向于动态查找，常用于文件系统中。 B 树中，节点的子树最大数目称为 B 树的阶。

数据结构可以看作是算法实现的容器，通过一系列特殊结构的数据集合，能够将算法更为高效而可靠的执行起来。 算法（Algorithm）是为了解决一个特定的问题而精心设计的一套数学模型以及在这套数学模型上的一系列操作步骤，这些操作步骤是将描述的输入数据逐步处理、转换，并最后得到一个确定的结果。 一般来说，算法设计没有什么固定的方法可循。但是通过大量的实践，也总结出算法某些共性的规律，包括枚举(Enumeration)、递归(Recursion)、分支法(Divide and Conquer)、贪心法(Greedy)、回溯法(Backtracking)、动态规划法(Dynamic Programming)等。

1. 枚举

枚举（Enumeration）又称暴力枚举，顾名思义，就是穷尽列举。基本思想是：按问题本身的性质，一一列举出该问题所有可能的解，并在逐一列举的过程中，检验每个可能的解是否真正的解，若是，就采纳，否则就放弃。

Trie 树，也叫“字典树”、“前缀树”。它是一种有序树形结构。是一种专门处理字符串匹配的数据结构，用来解决在一组字符串集合中快速查找某个字符串的问题。 AC 自动机以**Trie 树的结构为基础，结合KMP的思想**建立的，是一种用于解决多模式匹配问题的经典算法。

1. Trie 树

Trie 树的本质，就是利用字符串之间的公共前缀，将重复的前缀合并在一起。

介绍字符串匹配算法之前，先定义几个概念：

• 主串Text: 长度记作 n；
• 模式串Pattern: 长度记作 m，并且 m<=n。
• 有效位移s（Valid Shift）：即模式串在主串中出现，并且位置移动 s 次。

1. BF 算法

BF（Brute Force）算法，中文叫作暴力匹配算法，也叫朴素匹配算法。

二分查找（Binary Search）又称折半查找、二分搜索、折半搜索等，查找思想有点类似分治思想，对应的时间复杂度为O(logn)。 二分查找算法仅适用于有序且使用顺序存储结构的序列（比如有序数组）。 核心思想是：不断地缩小搜索区域，降低查找目标元素的难度。（每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为 0。）

• 以在升序序列中查找目标元素为例，二分查找算法的实现思路是：
  1. 初始状态下，将整个序列作为搜索区域（假设为 [B, E]）；
  2. 找到搜索区域内的中间元素（假设所在位置为 M），和目标元素进行比对。如果相等，则搜索成功；如果中间元素大于目标元素，将左侧 [B, M-1] 作为新的搜素区域；反之，若中间元素小于目标元素，将右侧 [M+1, E] 作为新的搜素区域；
  3. 重复执行第二步，直至找到目标元素。如果搜索区域无法再缩小，且区域内不包含任何元素，表明整个序列中没有目标元素，查找失败。

1. 标准二分查找

二分查找递归实现：