# 2016q3 Homework1 (phonebook)
contributed by <`atlantis0914`>

## 未優化版本

* Entry

typedef struct __PHONE_BOOK_ENTRY {
    char lastName[MAX_LAST_NAME_SIZE];
    char firstName[16];
    char email[16];
    char phone[10];
    char cell[10];
    char addr1[16];
    char addr2[16];
    char city[16];
    char state[2];
    char zip[5];
    struct __PHONE_BOOK_ENTRY *pNext;
} entry;

使用perf量測cache miss

         1,354,901      cache-misses #   68.477 % of all cache refs (73.93%)
         1,770,259      cache-references (75.52%)
       305,758,311      instructions #    1.21  insns per cycle (76.75%)
       258,470,718      cycles (75.60%)

       0.091748655 seconds time elapsed ( +-  0.74% )


## 使用B-Tree實做
* 介紹
* B-Tree(Bayer-McCreight, 1972):
參數為degree，或稱branching factor，表示一個node包含的children數量，B-Tree儲存的資料為key-value的組合，標準的B-Tree結構為（以degree ＝M為例）：

* Leaf: 
為key-value pair儲存的地方，可以儲存L個key-value pair，每個leaf的高度相同。

* Internal node:
為key儲存的地方，每個node最多可以儲存M-1個key，以及M/2至M個children。

* Root:
可以儲存2至M個children。

* 一個標準的B-Tree如下圖:


* 這次實作的B-Tree是針對phonebook做的修改，如下:

* 1\. Root、Internal node與Leaf均為同一種data type。
* 2\. 儲存的data以value取代標準的key-value pair。
* 3\. 實做部份參考了：
http://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/BTree.java.html
只是將Java用C語言改寫

* 以圖示來表達資料結構:

* Entry:

	typedef struct __BTREE_ENTRY {
		char lastName[MAX_LAST_NAME_NUM];
		struct __BTREE_NODE *pNext;
	} bTreeEntry;


* Node:

	typedef struct __BTREE_NODE {
	int degree;
	struct __BTREE_ENTRY children[DEGREE];
	} bTreeNode;

其中DEGREE為一個Node可以儲存的entry個數，相當於branching factor。


* 以下是B-Tree如何進行append(以DEGREE = 4為例):


此時root的degree已經等於DEGREE的值(DEGREE = 4)，root會分裂並且新增root如下:


繼續append...



此時左下角的Node已經滿了，必須分裂


繼續append



右下角的Node滿了，必須分裂


這時候Root滿了，同樣要再分裂


從圖中描述可以得知，B-Tree在append的過程是不斷的往上長。

**DEGREE = 64**

           721,939      cache-misses              #   76.656 % of all cache refs      (74.79%)
           922,121      cache-references                                              (75.07%)
     3,193,521,105      instructions              #    2.12  insns per cycle          (75.39%)
     1,503,996,958      cycles                                                        (75.03%)

       0.514395667 seconds time elapsed                                          ( +-  0.26% )


**DEGREE = 128**

           625,691      cache-misses              #   66.105 % of all cache refs      (74.92%)
           915,545      cache-references                                              (75.03%)
     4,722,925,716      instructions              #    2.21  insns per cycle          (75.16%)
     2,096,578,194      cycles                                                        (75.04%)

       0.747960187 seconds time elapsed                                          ( +-  0.65% )


* findName()的時間比之前的Unrolled linked list低了許多，但是append()的執行時間卻暴增許多，增加DEGREE的值又再增加append()的執行時間，推測原因為append()內使用了許多for loop所導致。

       改進方向:

* 減少append()所需的時間。
* 實作delete()。