图由结点的有穷结合V和边的集合E组成。为了与树形结构进行区别，在图结构中常常将结点称为顶点，边是顶点的有序偶对。若两个顶点之间存在一条边，则表示这两个顶点具有相邻的关系。

图通常有两种存储方式，即邻接矩阵和邻接表。

下面介绍一下邻接矩阵。设G=(V,E)是具有n个结点的图，顶点序号依次为0，1，2，3、、、n-1。G的邻接矩阵是具有如下定义的方阵A：

A[i][j]=1表示顶点i与顶点j邻接，即i与j之间有一条边或者弧。

A[i][j]=0表示顶点i与顶点j不邻接

邻接矩阵是图的顺序存储结构。

邻接矩阵的结构型定义如下：

struct VerType{
	
	int no;//顶点的编号 
	char info;//顶点的其他信息 
	
};
struct MGraph{
	
	int n,e;//结点数目与边数
	int edges[maxn][maxn];//邻接矩阵的定义 
	int VerType[maxn]; //存放结点的信息
	
};

关于邻接表的形式： 

struct ArcNode{
	int adjvex;//这条边所指向的结点信息
	struct ArcNode *nextarc;//该顶点指向下一条边的指针
	int info;//这条边的相关信息如权值 
}; 
struct VNode {
	char data;//顶点信息 
	ArcNode *firstarc;//指向第一条边的指针 
};
struct Agraph{
	
	VNode adjlist[maxn];//邻接表 
	int n,e;//顶点数目和边数 
};



 

(转自http://blog.csdn.net/x1247600186/article/details/24670775)
说到存储结构,我们就会想到常用的两种存储方式:顺序存储和链式存储两种。
先来看看顺序存储，用一段地址连续的存储单元依次存储线性表中数据元素，这对于线性表来说是很自然的，但是对于树这种一对多的结构而言是否适合呢？
树中某个结点的孩子可以有多个，这就意味着，无论用哪种顺序将树中所有的结点存储到数组中，结点的存储位置都无法直接反映逻辑关系，试想一下，数据元素挨个存储，那么谁是谁的双亲，谁是谁的孩子呢？所以简单的顺序存储是不能满足树的实现要求的。
不过可以充分利用顺序存储和链式存储结构的特点，完全可以实现对树的存储结构的表示。
下面介绍三种不同的树的表示法:双亲表示法,、孩子表示法,、孩子兄弟表示法。
1、双亲表示法：
我们假设以一组连续空间存储树的结点，同时在每个结点中，附设一个指示器指向其双亲结点到链表中的位置。也就是说每个结点除了知道自己之外还需要知道它的双亲在哪里。
它的结构特点是如图所示：
以下是我们的双亲表示法的结构定义代码：
/*树的双亲表示法结点结构定义  */
#define MAXSIZE 100
typedef int ElemType;       //树结点的数据类型，暂定为整形
typedef struct PTNode       //结点结构
{
ElemType data;          //结点数据
int parent;             //双亲位置
}PTNode;
typedef struct
{
PTNode nodes[MAXSIZE];  //结点数组
int r,n;                //根的位置和结点数
}PTree;
2、孩子表示法
换一种不同的考虑方法。由于每个结点可能有多棵子树，可以考虑使用多重链表，即每个结点有多个指针域，其中每个指针指向一棵子树的根结点，我们把这种方法叫做多重链表表示法。不过树的每个结点的度，也就是它的孩子个数是不同的。所以可以设计两种方案来解决。
方案一：
一种是指针域的个数就等于树的度(树的度是树的各个结点度的最大值)
其结构如图所示：
不过这种结构由于每个结点的孩子数目不同，当差异较大时，很多结点的指针域就都为空，显然是浪费空间的，不过若树的各结点度相差很小时，那就意味着开辟的空间都被利用了，这时这种缺点反而变成了优点。
方案二：
第二种方案是每个结点指针域的个数等于该结点的度，我们专门取一个位置来存储结点指针域的个数。
其结构如图所示：
这种方法克服了浪费空间的缺点，对空间的利用率是很高了，但是由于各个结点的链表是不相同的结构，加上要维护结点的度的数值，在运算上就会带来时间上的损耗。
能否有更好的方法呢，既可以减少空指针的浪费，又能是结点结构相同。
说到这大家肯定就知道是有的麦，那就是孩子表示法。
具体办法是，把每个结点的孩子排列起来，以单链表做存储结构，则n个结点有n个孩子链表，如果是叶子结点则此单链表为空。然后n个头指针有组成一个线性表，采用顺序存储结构，存放进入一个一维数组中。
为此，设计两种结点结构，
一个是孩子链表的孩子结点，如下所示：
其中child是数据域，用来存储某个结点在表头数组中的下标。next是指针域，用来存储指向某结点的下一个孩子结点的指针。
另一个是表头结点，如下所示：
其中data是数据域，存储某结点的数据信息。firstchild是头指针域，存储该结点的孩子链表的头指针。
以下是孩子表示法的结构定义代码：
/*树的孩子表示法结点结构定义  */
#define MAXSIZE 100
typedef int ElemType;       //树结点的数据类型，暂定为整形
typedef struct CTNode       //孩子结点
{
int child;
struct CTNode *next;
}*ChildPtr;
typedef struct              //表头结构
{
ElemType data;
ChildPtr firstchild;
}CTBox;
typedef struct              //树结构
{
CTBox nodes[MAXSIZE];   //结点数组
int r,n;                //根结点的位置和结点数
}CTree;
3、孩子兄弟表示法
我们发现，任意一颗树，它的结点的第一个孩子如果存在就是的，它的右兄弟如果存在也是唯一的。因此，我们设置两个指针，分别指向该结点的第一个孩子和此结点的右兄弟。
其结点结构如图所示：
以下是孩子兄弟表示法的结构定义代码：
/*树的孩子兄弟表示法结构定义 */
typedef struct CSNode
{
ElemType  data;
struct CSNode  *firstchild, *rightsib;
}CSNode, *CSTree;

今天对比一下mysql两种常用存储引擎myisam和innodb的文件存储结构： 

先说一下两者的大概区别： 

myisam 更适合读取大于写入的业务，同时不支持事物。 

innodb 支持事物，效率上比myisam稍慢。

文件存储：

 

myism物理文件结构为：



.frm文件：与表相关的元数据信息都存放在frm文件，包括表结构的定义信息等。

.myd文件：myisam存储引擎专用，用于存储myisam表的数据

.myi文件：myisam存储引擎专用，用于存储myisam表的索引相关信息

innodb的物理文件结构为：



.frm与表相关的元数据信息都存放在frm文件，包括表结构的定义信息等。 

.ibd文件和.ibdata文件： 

这两种文件都是存放innodb数据的文件，之所以用两种文件来存放innodb的数据，是因为innodb的数据存储方式能够通过配置来决定是使用共享表空间存放存储数据，还是用独享表空间存放存储数据。

独享表空间存储方式使用.ibd文件，并且每个表一个ibd文件

共享表空间存储方式使用.ibdata文件，所有表共同使用一个ibdata文件

觉得使用哪种方式的参数在mysql的配置文件中 innodb_file_per_table

 

 

 

图的四种存储结构
因为图的任意两个顶点间都可能存在联系，因此无法通过数据元素在存储区中的物理位置来表示元素之间的关系，即图没有顺序存储结构，但是我们可以用二维数组（矩阵）来表示元素之间的关系——邻接矩阵。除此之外还有链式存储结构，包括邻接表、十字链表和邻接多重表。在这些方法中，邻接矩阵和邻接表最常用。
一、邻接矩阵法

图的邻接矩阵的存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组（称为邻接矩阵）存储图中的边或弧的信息（可分别称他们为顶点数组和边数组）。设图G有n个顶点，则邻接矩阵是一个nxn的方阵。在无向图中，求某个顶点的度，即计算此顶点vi在邻接矩阵中第i行（或第i列）的元素之和。若vi到vj之间有通路，则记为1，反之为0。在有向图中，求某个顶点vi的出度，即求此顶点所在行的元素之和，若求某个顶点的如度，即求顶点所在列的元素之和。







存储空间：

无向图：n(n-1)/2

有向图（网）：n^2

二、邻接链表法

对图中的每个顶点建立一个单链表，存储该顶点所有邻接顶点及其相关信息。每一个单链表设有一个表头结点。第i个单链表中的结点依附于顶点Vi的边。在求无向图的度时，只要找出此节点对应的单链表中的节点个数之和即可。但是就有向图而言，其又分为入度和出度，在邻接表中，结点vi对应的单链表中，其表示的是以vi为起点的所能到达的节点，即其对应的结点总数为此节点的出度。要想求起入度，则需要建立逆邻接表(如布简历逆邻接表，则需要扫描整个邻接表才能得出)，此时，vi对应的单链表表示的是以vi为终点，以单链表中的结点作为起点的通路，故单链表中的结点总数表示的是vi的入度。









存储空间：

无向图：n+2e

有向图：n+e
三、十字链表法

对于有向图来说，邻接表虽然解决了出度问题，但是如果我们想要计算入度时则需要遍历整个图才能知道结果。而逆邻接表，它虽然解决了入度问题，但是他计算出度时又很不易。因此十字链表法应运而生，他将邻接表和逆邻接表相结合，从而时的出度和入度的计算变得容易起来。

十字链表是有向图的另一种链式存储结构，其顶点和弧分别各用一种存储结构的结点表示。弧头相同的弧被链在同一链表上，弧尾相同的弧也被链在同一链表上，链表的头结点就是顶点结点。是有向图的邻接表与逆邻接表结合起来的一种链表。在十字链表中容易找到以vi（vi∈G(V)）为弧尾或弧头的弧，容易求顶点的入度和出度。



四、多重链表法

邻接多重链表是无向图的另一种链式存储结构。其顶点和弧分别各用一种存储结构的结点表示。依附于相同顶点的边被链在同一链表上，每条边依附于两个结点，所以每个边结点被同时链接在两个单链表中。链表的头结点就是顶点结点。此外，还在边结点中增加了一个标志位。用以标记该条边是否被搜索过，避免了同一条边的重复搜索。对无向图而言，邻接表的缺点：每一条边(va,vb)有两个结点，分别在第a和第b个单链表中，这可能会给边的搜索、删除等操作带来了不便。邻接多重表与邻接表的区别仅在于，同一条边，在邻接表中要用两个结点表示，而在邻接多重表中只需要一个结点。



十字链表和多重链表分别是对有向图邻接表和无向图邻接表的补充