189 8069 5689
这篇文章主要讲解了“PostgreSQL数据库实现原理是什么”，文中的讲解内容简单清晰，易于学习与理解，下面请大家跟着小编的思路慢慢深入，一起来研究和学习“PostgreSQL数据库实现原理是什么”吧！
PostgreSQL的FSM文件,其数据结构基础是大堆二叉树,构建/删除/插入的相关代码详见代码注释.
#include "heap.h"
static int heap[MAX_ELEMENTS];
static int counter = 0;
//交换数据
static void swap(int *i,int *j)
{
int tmp = *j;
*j = *i;
*i = tmp;
}
//打印堆信息
//n : 元素个数
void print_max_heap()
{
for(int i = 1;i <= counter;i++)
{
printf("item[%d] is %d\n",i,heap[i]);
}
}
//初始化堆数组
void init_heap(int *array,int n)
{
for(int i=0;i < n;i++)
{
heap[i] = array[i];
}
counter = n;
}
//插入到大堆
//item : 插入的值
//*n : 堆元素个数
void insert_max_heap(int item)
{
if(HEAP_FULL(counter)){
return;
}
//整个算法思想是首先把插入的值放在堆中的最后一个位置,然后为其找到合适的位置(递归向上)
int i = ++counter;
//i ≠ 1是因为数组的第一个元素并没有保存堆结点
for(;(i != 1) && (item > heap[i/2]);i = i / 2){
//如果插入的值比其父节点要大,把父节点的值交互到当前节点
heap[i] = heap[i/2];//这里其实和递归操作类似，就是去找父结点
}
//父节点的值比当前值要大或者已到达根节点,设置当前位置的值为要插入的值
heap[i] = item;
}
//删除大堆中的元素
//*n : 堆元素个数
void delete_max_heap()
{
//删除大堆,总是删除大堆的根节点
if(HEAP_EMPTY(counter))
{
return;
}
//算法思想 : 把最后一个元素作为根节点,然后寻找该节点在树中合适的位置
int lastone = heap[--counter];
//父节点,初始化为1
int parent = 1;
for (int son=parent*2;son <= counter;son=son*2)
{
//删除父节点后,比较左右子节点的大小
if(son < counter && heap[son] < heap[son+1])
{
//如果右子节点大于左子节点,切换到右子节点
son++;
}
if (lastone > heap[son])
{
break;//已经比儿子要大,退出
}
//把子节点移到父节点
//parent的位置就是lastone移动到的位置
heap[parent]=heap[son];
//递归,到下一层子树
parent = son;
}
//parent的位置就是最后一个元素所在的位置
heap[parent]=lastone;//lastone的实际位置已找到,赋值
}
//构建大堆
//n : 元素个数
//heap是初始化但未构建的数组
void build_max_heap()
{
for(int i = counter;i > 1;i--)
{
//从最后一个元素(最下层)开始遍历数组
if(heap[i] > heap[i/2])
{
//子节点比父节点要大,交换父子节点
swap(&(heap[i/2]),&(heap[i]));
for(int j=i*2;j < counter;j=j*2)
{
//递归处理子节点
if (j > counter)
{
break;
}
if(j < counter && heap[j+1] > heap[j])
{
//切换至右子节点
j++;
}
if (heap[j] > heap[j/2])
{
//如果子节点大于父节点,交换
swap(&(heap[j/2]),&(heap[j]));
}
}//end for#2
}//end if
}//end for#1
}
void build_max_heap_new()
{
for(int i = counter/2;i > 1;i--)
{
//从子节点上一层开始处理
//父节点为i
int parent=i;
//该节点的值
int temp=heap[parent];
for(int child=parent*2;child <=counter;child=child*2)
{
//
if(child < counter && heap[child] < heap[child+1])
{
//切换到右子节点
child++;
}
if(temp > heap[child])
//父节点比子节点大,退出该父节点构成的树循环
break;
else
{
//把子节点的值放到父节点中
heap[parent] = heap[child];
}
//进入到子节点,递归处理
parent = child;
}
//已找到该父节点合适的位置,赋值
heap[parent]=temp;
}//end for#1
}感谢各位的阅读，以上就是“PostgreSQL数据库实现原理是什么”的内容了，经过本文的学习后，相信大家对PostgreSQL数据库实现原理是什么这一问题有了更深刻的体会，具体使用情况还需要大家实践验证。这里是创新互联，小编将为大家推送更多相关知识点的文章，欢迎关注！