数据库自动分配算法

1. 什么是基于索引搜索 动态分配算法

倒排索引表中的每一项都包括一个属性值和具有该属性值的各记录的地址。由于不是由记录来确定属性值，而是由属性值来确定记录的位置，因而称为倒排索引(inverted index)。带有倒排索引的文件我们称为倒排索引文件，简称倒排文件。建立全文索引中有两项非常重要，一个是如何对文本进行分词，一是建立索引的数据结构。分词的方法基本上是二元分词法、最大匹配法和统计方法。索引的数据结构基本上采用倒排索引的结构。
分词的好坏关系到查询的准确程度和生成的索引的大小。在中文分词发展中，早期经常使用分词方式是二元分词法，该方法的基本原理是将包含中文的句子进行二元分割，不考虑单词含义，只对二元单词进行索引。因此该方法所分出的单词数量较多，从而产生的索引数量巨大，查询中会将无用的数据检索出来，好处是算法简单不会漏掉检索的数据。之后又发展出最大匹配分词方法，该方法又分为正向最大分词和逆向最大分词。其原理和查字典类似，对常用单词生成一个词典，分析句子的过程中最大的匹配字典中的单词，从而将句子拆分为有意义的单词链。最大匹配法中正向分词方法对偏正式词语的分辨容易产生错误，比如“首饰和服装”会将“和服”作为单词分出。达梦数据库采用的是改进的逆向最大分词方法，该分词方法较正向正确率有所提高。最为复杂的是通过统计方式进行分词的方法。该方法采用隐式马尔科夫链，也就是后一个单词出现的概率依靠于前一个单词出现的概率，最后统计所有单词出现的概率的最大为分词的依据。这个方法对新名词和地名的识别要远远高于最大匹配法，准确度随着取样文本的数量的增大而提高。
二元分词方法和统计方法是不依赖于词典的，而最大匹配法分词方法是依赖于词典的，词典的内容决定分词结构的好坏。
全文检索的索引被称为倒排索引，之所以成为倒排索引，是因为将每一个单词作为索引项，根据该索引项查找包含该单词的文本。因此，索引都是单词和唯一记录文本的标示是一对多的关系。将索引单词排序，根据排序后的单词定位包含该单词的文本。
步骤1）读取一整条句子到变量str中，转到步骤2

步骤2）从句子的尾端读取1个字到变量word中，转到步骤3

步骤3）在字典查找word中保存的单词。如果存在则保存word，转到步骤4，否则转到步骤5）

步骤4）如果是字典中最大单词或者超过最大单词数（认定为新词），从句尾去掉该单词，返回步骤2

步骤5）读取前一个字到word中，构成新单词，转到步骤3）

词库的内存数据结构和词库中单词的匹配算法

内存中单词采用层次结构保存

2. 数据库分库分表（二）Twitter-Snowflake（64位分布式ID算法）分析与JAVA实现

Twitter-Snowflake算法产生的背景相当简单，为了满足Twitter每秒上万条消息的请求，每条消息都必须分配一条唯一的id，这些id还需要一些大致的顺序（方便客户端排序），并灶核且在掘顷分布式系统中不同机器产生的id必须不同。各种主键ID生成策略对比，见 常见分布式主键ID生成策略

把 41位的时间前缀 ， 10位的节点标识 ， 12位的sequence 组合在一起。
除了最高位bit标记为不可用以外，其余三组bit占位均可浮动，看具体的业务需求而定。 默认情况下41bit的时间戳，1970年算起可以支持该算法使用到2038年，10bit的工作机器id可以支持1024台机器，序列号支持1毫秒产生4096个自增序列id 。

Snowflake是Twitter在2010年用Scala语言写的一套主键生成策略，用Thrift对外发布主键生成服务，其中依赖了Twitter内部的Infrastructure，后来Twitter用 Twitter-server 代替了Snowflake，自2012年起就未更新。见 Twitter-Snowflake项目地址（Tags:snowflake-2010）
之前写了一个Java的实现，改自网上一个版本: Twitter的分布式自增ID算法Snowflake实现分析及其Java、Php和Python版 。后来看到当当网的 Sharding-JDBC 分库分表中间件已实现了此算法。就直接在其中添隐散掘加了一些新特性，已merge。( 具体实现 , 说明文档 )
添加3种IdGenerator实现。

用笔记本（i7-3632QM 2.2GHz 四核八线程）测试了下，每秒生成409万（理论上的峰值），CPU占用率18.5%。

3. 数据库技术知识数据结构的算法

数据库技术知识数据结构的算法

对于将要参加计算机等级考试的考生来说，计算机等级考试的知识点辅导是非常重要的复习资料。以下是我收集的数据库技术知识数据结构的算法，希望大家认真阅读!

1、数据：数据的基本单位是数据元素。数据元素可由一个或多个数据项组成。数据项是数据的不可分割的最小单位

2、数据结构：数据的逻辑结构、数据的存储结构、数据的运算

3、主要的数据存储方式：顺序存储结构(逻辑和物理相邻，存储密度大)和链式存储结构

顺序存储结构：

顺序存储计算公式 Li=L0+(i-1)×K 顺序结构可以进行随机存取;插人、删除运算会引起相应节点的大量移动

链式存储结构：a、指针域可以有多个，可以指向空，比比顺序存储结构的存储密度小

b、逻辑上相邻的节点物理上不一定相邻。 c、插人、删除等不需要大量移动节点

4、顺序表：一般情况下，若长度为n的顺序表，在任何位置插入或删除的概率相等，元素移动的平均次数为n/2(插入)和(n-1)/2(删除)。

5、链表：线性链表(单链表和双向链表等等)和非线性链表

线性链表也称为单链表，其每个一节点中只包含一个指针域，双链表中，每个节点中设置有两个指针域。(注意结点的插入和删除操作)

6、栈：“后进先出”(LIFO)表。栈的应用：表达式求解、二叉树对称序周游、快速排序算法、递归过程的实现等

7、队列：“先进先出”线性表。应用：树的层次遍历

8、串：由零个或多个字符组成的有限序列。

9、多维数组的顺序存储：

10、稀疏矩阵的存储：下三角矩阵顺序存储

其他常见的存储方法还有三元组法和十字链表法

11、广义表：由零个或多个单元素或子表所组成的有限序列。广义表的元素可以是子表，而子表的元素还可以是子表

12、树型结构：非线性结构。常用的树型结构有树和二叉树。

二叉树与树的区别：二叉树不是树的特殊情况，树和二叉树之间最主要的区别是：二叉树的节点的子树要区分左子树和右子树，即使在节点只有一棵子树的情况下也要明确指出该子树是左子树还是右子树。

13、树(森林)与二叉树之间的转换(要会转换)

14、二叉树和树的周游(遍历)

二叉树的周游主要有以下3种方式：前序法(NLR)、对称序法(LNR)、后序法(LRN)

周游树和树林：深度优先和按广度优先两种方式进行。深度优先方式又可分为按先根次序和按后根次序周游

树与二叉树周游之间的对应关系：按先根次序周游树正好与按前序法周游树对应的二叉树等同，后根次序周游树正好与按对称序法周游对应的`二叉树等同

按广度优先方式就是层次次序周游

15、二叉树的存储和线索

二叉树的存储结构：二叉树的llink一rlink法存储表示

线索二叉树：在有n个节点的二叉树的且llink - rlink法存储表示中，必定有n+1个空指针域

16、哈夫曼树：一类带权路径长度最短的树。树的带权路径长度为树中所有叶子节点的带权路径长度之和WPL。

17、查找：

(1)顺序查找：平均查找长度为(n +1 )/2次，时间复杂度为O(n)

(2)二分法查找：线性表节点必须按关键码值排序，且线性表是以顺序存储方式存储的。查找成功比较次数log2n，查找失败比较次数log2n+1

(3)分块查找：先是块间查找，然后块内查找。

(4)散列表(哈希表Hash)的存储和查找：处理冲突的方法：开地址法(线性探测法)、拉链法等

负载因子(装填因子)=表实际存储的结点个数/表的最大能存储结点个数(即表长)

二叉排序树：每个结点左子树的所有关键码值都小于该结点关键码值，右子树所有结点关键码值都大于该结点关键码值。对称周游二叉排序树，得到一个有序序列，时间复杂度O(log2n)

B树和B+树：M阶树，每个结点至多有M-1个关键码，至少有M/2(取上界)-1个关键码。B树适合随机查找，不适合顺序查找。B+树适合顺序查找。

18、排序

直接插人排序、希尔排序、直接选择排序、堆排序、起泡排序、快速排序等排序算法要了解。

直接选择排序、希尔排序、快速排序和堆排序是不稳定排序，其他排序为稳定排序