PostgreSQL數(shù)據(jù)庫(kù)實(shí)現(xiàn)原理是什么

這篇文章主要講解了“PostgreSQL數(shù)據(jù)庫(kù)實(shí)現(xiàn)原理是什么”，文中的講解內(nèi)容簡(jiǎn)單清晰，易于學(xué)習(xí)與理解，下面請(qǐng)大家跟著小編的思路慢慢深入，一起來(lái)研究和學(xué)習(xí)“PostgreSQL數(shù)據(jù)庫(kù)實(shí)現(xiàn)原理是什么”吧！

PostgreSQL的FSM文件,其數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)是最大堆二叉樹(shù),構(gòu)建/刪除/插入的相關(guān)代碼詳見(jiàn)代碼注釋.

#include "heap.h"
static int heap[MAX_ELEMENTS];
static int counter = 0;
//交換數(shù)據(jù)
static void swap(int *i,int *j)
{ 
  int tmp = *j;
  *j = *i;
  *i = tmp;
}
//打印堆信息
//n : 元素個(gè)數(shù)
void print_max_heap()
{
  for(int i = 1;i <= counter;i++)
  {
     printf("item[%d] is %d\n",i,heap[i]);
  }
}
//初始化堆數(shù)組
void init_heap(int *array,int n)
{
  for(int i=0;i < n;i++)
  {
    heap[i] = array[i];
  }
  counter = n;
}
//插入到最大堆
//item : 插入的值
//*n : 堆元素個(gè)數(shù)
void insert_max_heap(int item)
{
    if(HEAP_FULL(counter)){
      return;
    }
    //整個(gè)算法思想是首先把插入的值放在堆中的最后一個(gè)位置,然后為其找到合適的位置(遞歸向上)
    int i = ++counter;
    //i ≠ 1是因?yàn)閿?shù)組的第一個(gè)元素并沒(méi)有保存堆結(jié)點(diǎn)
    for(;(i != 1) && (item > heap[i/2]);i = i / 2){
      //如果插入的值比其父節(jié)點(diǎn)要大,把父節(jié)點(diǎn)的值交互到當(dāng)前節(jié)點(diǎn)
      heap[i] = heap[i/2];//這里其實(shí)和遞歸操作類似，就是去找父結(jié)點(diǎn)
    }
    //父節(jié)點(diǎn)的值比當(dāng)前值要大或者已到達(dá)根節(jié)點(diǎn),設(shè)置當(dāng)前位置的值為要插入的值
    heap[i] = item;
}
//刪除最大堆中的元素
//*n : 堆元素個(gè)數(shù)
void delete_max_heap()
{
  //刪除最大堆,總是刪除最大堆的根節(jié)點(diǎn)
  if(HEAP_EMPTY(counter))
  {
     return;
  }
  //算法思想 : 把最后一個(gè)元素作為根節(jié)點(diǎn),然后尋找該節(jié)點(diǎn)在樹(shù)中合適的位置
  int lastone = heap[--counter];
  //父節(jié)點(diǎn),初始化為1
  int parent = 1;
  for (int son=parent*2;son <= counter;son=son*2)
  {
    //刪除父節(jié)點(diǎn)后,比較左右子節(jié)點(diǎn)的大小
    if(son < counter && heap[son] < heap[son+1])
    {
      //如果右子節(jié)點(diǎn)大于左子節(jié)點(diǎn),切換到右子節(jié)點(diǎn)
      son++;
    }
    if (lastone > heap[son])
    {
      break;//已經(jīng)比兒子要大,退出
    }
    //把子節(jié)點(diǎn)移到父節(jié)點(diǎn)
    //parent的位置就是lastone移動(dòng)到的位置
    heap[parent]=heap[son];
    //遞歸,到下一層子樹(shù)
    parent = son;
  }
  //parent的位置就是最后一個(gè)元素所在的位置
  heap[parent]=lastone;//lastone的實(shí)際位置已找到,賦值
}
//構(gòu)建最大堆
//n : 元素個(gè)數(shù)
//heap是初始化但未構(gòu)建的數(shù)組
void build_max_heap()
{
  for(int i = counter;i > 1;i--)
  {
    //從最后一個(gè)元素(最下層)開(kāi)始遍歷數(shù)組
    if(heap[i] > heap[i/2])
    {
      //子節(jié)點(diǎn)比父節(jié)點(diǎn)要大,交換父子節(jié)點(diǎn)
      swap(&(heap[i/2]),&(heap[i]));
      for(int j=i*2;j < counter;j=j*2)
      {
        //遞歸處理子節(jié)點(diǎn)
        if (j > counter)
        {
          break;
        }
        if(j < counter && heap[j+1] > heap[j])
        {
          //切換至右子節(jié)點(diǎn)
          j++;
        }
        if (heap[j] > heap[j/2])
        {
          //如果子節(jié)點(diǎn)大于父節(jié)點(diǎn),交換
          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--)
  {
    //從子節(jié)點(diǎn)上一層開(kāi)始處理
    //父節(jié)點(diǎn)為i
    int parent=i;
    //該節(jié)點(diǎn)的值
    int temp=heap[parent];
    for(int child=parent*2;child <=counter;child=child*2)
    {
      //
      if(child < counter && heap[child] < heap[child+1])
      {
        //切換到右子節(jié)點(diǎn)
        child++;
      }
      if(temp > heap[child])
        //父節(jié)點(diǎn)比子節(jié)點(diǎn)大,退出該父節(jié)點(diǎn)構(gòu)成的樹(shù)循環(huán)
        break;
      else
      {
        //把子節(jié)點(diǎn)的值放到父節(jié)點(diǎn)中
        heap[parent] = heap[child];
      }
      //進(jìn)入到子節(jié)點(diǎn),遞歸處理
      parent = child;
    }
    //已找到該父節(jié)點(diǎn)合適的位置,賦值
    heap[parent]=temp;
  }//end for#1
}

感謝各位的閱讀，以上就是“PostgreSQL數(shù)據(jù)庫(kù)實(shí)現(xiàn)原理是什么”的內(nèi)容了，經(jīng)過(guò)本文的學(xué)習(xí)后，相信大家對(duì)PostgreSQL數(shù)據(jù)庫(kù)實(shí)現(xiàn)原理是什么這一問(wèn)題有了更深刻的體會(huì)，具體使用情況還需要大家實(shí)踐驗(yàn)證。這里是億速云，小編將為大家推送更多相關(guān)知識(shí)點(diǎn)的文章，歡迎關(guān)注！