数据结构

数据在内存中如何放 便于检索 数据结构 常见的数据结构:

1. 数组
2. 栈
3. 队列
4. 链表
5. 图
6. 树
7. 前缀树
8. 哈希表

所谓协议就是通讯双方都需要安装的数据结构来收发数据.

内存其实就是连续的存储单元组成的，我们常见的数据结构（二叉树、链表之类）在内存中的存储其实都是也是一个一个安放的（物理结构），只是人为的我们赋予了不同的意义（逻辑结构）。

顺序储存

在计算机中用一组地址连续的存储单元依次储存线性表的各个数据元素,称为线性表的顺序储蓄结构.

特点

随机存取表中元素

插入和删除操作需要移动元素

链接存储

在计算机中用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的,也可以是不连续的)。它不要求逻辑上相邻的元素在物理位置上也相邻.因此它没有顺序存储结构所具有的弱点,但也同时失去了顺序表可随机存取的优点。特点：

比顺序存储结构的存储密度小 (每个节点都由数据域和指针域组成，所以相同空间内假设全存满的话顺序比链式存储更多)。
逻辑上相邻的节点物理上不必相邻。
插入、删除灵活 (不必移动节点，只要改变节点中的指针)。
查找结点时链式存储要比顺序存储慢。
每个结点是由数据域和指针域组成。

索引存储

除建立存储结点信息外，还建立附加的索引表来标识结点的地址。索引表由若干索引项组成。特点：

索引存储结构是用结点的索引号来确定结点存储地址，其优点是检索速度快，缺点是增加了附加的索引表,会占用较多的存储空间。在数据表中，就是用索引键来进行存储与检索的。

散列存储

散列存储，又称hash存储，是一种力图将数据元素的存储位置与关键码之间建立确定对应关系的查找技术。

散列法存储的基本思想是：由节点的关键码值决定节点的存储地址。散列技术除了可以用于查找外，还可以用于存储。特点：

散列是数组存储方式的一种发展，相比数组，散列的数据访问速度要高于数组，因为可以依据存储数据的部分内容找到数据在数组中的存储位置，进而能够快速实现数据的访问，理想的散列访问速度是非常迅速的，而不像在数组中的遍历过程，采用存储数组中内容的部分元素作为映射函数的输入，映射函数的输出就是存储数据的位置，这样的访问速度就省去了遍历数组的实现，因此时间复杂度可以认为为O(1)，而数组遍历的时间复杂度为O(n)。

散列(hashing)是一种重要的存储方法，也是一种常见的查找方法。

基本思想：以结点的关键字k为自变量，通过一个确定的函数关系f，计算出对应的函数值，吧这个函数值解释为结点的存储地址，将结点存入到f(k)所指示的存储位置上，在查找时再根据要查找的关键字，用同样的函数计算地址，然后到相应的单元中读取。散列法又被成为关键字——地址转换法。

顺序表的特点是：寻址容易，插入和删除困难； 而链表的特点是：寻址困难，插入和删除容易。 这个世界上有没有一种能够综合两者优点的，既寻址容易又插入和删除容易的数据结构？Yes，它就是Hash表。

哈希表

用散列法存储的线性表被称为哈希表，使用的函数被称为散列函数或者哈希函数，f(k)被称为散列地址或者哈希地址。通常情况下，散列表的存储空间是一个一维数组，而其哈希地址为数组的下标

哈希函数的选择原则

若哈希函数是一个一一对应的函数，则在查找时，只需要根据哈希函数对给定关键字的某种运算得到待查找结点的存储位置，无需进行比较

一般情况下，散列表的空间要比结点的集合大，虽然浪费了一部分空间但是却提高了查找的效率，散列表空间为m，填入表中结点数为n，则比值n/m成为哈希表的装填因子，一般取0.65~0.9之间

哈希函数应当尽量简单，其值域必须在表长的范围之内，尽量不要产生“冲突”(两个关键字得到相同的哈希地址)

Hash表优缺点

Hash表存在的优点显而易见，能够在常数级的时间复杂度上进行查找，并且插入数据和删除数据比较容易。但是它也有某些缺点，比如不支持排序，一般比用线性表存储需要更多的空间，并且记录的关键字不能重复。

数据库

内存中 红黑树比b树效率高 ,涉及磁盘操作 b树会更优

数据结构是数据间的有机关系,而算法是对数据的操作步骤.

数据结构并不是一门语言,他是一种思想,一种方法,一种思维方式

透过表象看本质，数据库就是存储数据的，那么就是 数据结构+处理方式

看看各种数据库的数据结构，看看处理方式，你就懂优缺点，而且还可以知道何时用哪种数据库

数据结构无非： 关系型/文档型/键值对型/三元存储/图存储

更细化一些：链表/tree/b-tree/红黑-tree/hash/图 等等

处理方式：sql/mapreduce/hashcode/批处理/消息流