#33 資料庫基礎 - 什麼是 Index

Index 在資料庫的領域裡算是很基本且極為重要的項目，因為它幫助我們可以在龐大的資料裡快速地找到資料．這一篇文章就來說明 Index 運作的原理． Index 也是一種典型的用空間換取時間的做法．這感覺就像是書籍裡最後面會有一些專有名詞在那一個頁數中可以找到，透過書籍的 Index，你可以很快找到你要找的專有名詞．同樣的，在資料庫裡也是類似像這樣的做法．資料庫引擎可以將你感興趣的資料製做成 Index，如此一來，資料庫引擎只要在 Index 上尋找目標，就可以很快速地得知該筆資料的位置是在資料庫檔案裡的什麼地方．這些就是 Index 概念．舉個例子，在資料庫裡有一個學生資料的表格，表格的...

閱讀全文

#32 資料庫基礎 - 資料讀取的成本評估

在前面的文章裡曾提供當資料庫引擎要儲存資料時可能有三種方式可以選擇，分別是 heap file, sorted file, 和 hashed file. Heap file基本上就是沒依照任何的規則來儲存資料，也就是說你先把資料A寫進去，然後再寫資料B，則自然而然地 A 的位置就會在 B 的前面．正常情況下，我們似乎不太希望用這種方式來儲存資料，因為它對資料搜找的速度上並沒有什麼幫助． 所以，假設資料一共分佈在 p 個 pages，然後每個 page 的讀取或寫入的平均時間為 d，那麼在尋找資料時所花費的成本便是 p*d，這是以最壞的情況來看的，因為我們無法知道我們要找的資料是在前面的 page 還是後面的 page，所以在成本評估時就用最壞的情況來看． 如果做 insert 動作，heap...

閱讀全文

#31 程式該怎麼分辨好壞呢 ?

上個星期看到一篇短文，文章網址如下 http://buzzorange.com/techorange/2015/10/08/the-six-most-common-species-of-code/ 這文章很有趣，它列出不同的人會如何寫出同一個 function． 看到學生寫的就是很標準的學生該有的答案．儘管 recursive 的寫法會有 call stack overflow 的問題，但對一個學生來說，重點是練習 recursive 的思考，所以這樣寫蠻好的． 看到由 Hackathon 寫出來的答案，哈哈，老實說，我真的是打從心裡笑了出來．這個笑可不是嘲笑的笑，而是一種打從心裡佩服的笑，尤其是看到那一句註解 // good enough for the demo 再來看看新創公司寫出來的，其實看不出來這和學生寫的有什麼大差別．也許作者在暗示些什麼? 再來看看大公司．還真的是有大公司寫法的樣子．你是否曾想過大公司的寫法為何是這樣子呢...

閱讀全文

#30 Coding面試 - LeetCode #125 Valid Palindrome

題目的網址: https://leetcode.com/problems/valid-palindrome/ 這一種題目算是蠻基本的，以前在台灣找工作時曾遇過有個公司的考卷出這一題，而在美國找工作時，目前還沒遇過有人考這一題或是相似的題目． 基本上，這題就是要寫一個 function 來驗證輸入的字串參數是不是 palindrome．所謂的 palindrome 就是字串中第一個位置和最後一個位置的值是一樣，第二個位置和倒數第二個位置的值是一樣，以此類推．所以一個很簡單的想法就是只要一個 for loop 就可以做完這樣的工作，而且不需要線性成長的空間，因此時間上是 O(n)，空間上是O(1)，這是對答案的要求了． 但 LeetCode 出的這一題有一點點小小的變化，因為輸入字串中可能會有其他的符號，而這些符號是不列入規則的，所以題目上寫 "A...

閱讀全文

#29 測試，該如何開始 ?

對一個好品質的軟體而言，測試的確是件很重要的事情．你寫的程式是否能在你假設的情況下做出正確的反應，這也是許多軟體工程師們的挑戰．一般較年輕的軟體工程師們往往過於著重在寫程式的技巧，所以常常忽略了花時間在學習如何測試你的程式．其實，軟體測試的學問完全不亞於一般的軟體開發所需的知識，而很多人可能會有一個先入為主的想法，那就是程式如何都寫不出來了，那學如何測試有什麼用呢 ? 聽起來好像還有幾分道理，至少在十多年前我是這樣想的．後來接觸多了之後也漸漸發現，如何不知道如何測試的話，那你怎麼能知道你寫出來的程式一定能用呢 ? 一般來說 (至少在我的工作環境下是如此)，軟體工程師自己寫出來的 function 一定要自己寫好 unit test．這是蠻重要的事情，因為除了你，應該沒有人比你更了解你寫的...

閱讀全文

#28 資料庫基礎 - 存取 Page (Hashed File)

前面兩篇文章提到了存取 page 的兩種方式，在這一篇文章裡要介紹的是另一種方式，我們稱它為 hashed file．聽到這個名字，你可能已經猜到這是和 hash function 有關係的儲存方式．沒錯，它就是利用 hash function 來決定儲存位置，也是就說透過 hash function 的計算來決定要儲存到那一個 page 上． 前面的文章曾提到過基本的 hash function，也介紹了它最簡單的運算方式．所以，假設一開始有十個 page，然後有五筆資料，我們可以將每筆資料傳給 hash function，計算出來的結果是...

閱讀全文

#27 Coding 面試 Leetcode #98 Validate Binary Search Tree

我記得這一題我被問過兩次，是兩個不同的團隊，而且都是跟資料庫有關的工作．所以，若你也要尋找資料庫相關的開發工作，看來 Tree 的題目是很難避免的． 這題的題目很單純，就是要寫一個 function 用來驗證題目的 Tree 是不是 Binary Search Tree (BST). 根據 BST 的定義，左邊的節點值必需小於父節點值，而右邊的節點值必需大於父節點值. 但這題有一點要小心的是，別只是檢查父節點值而己，應該要檢查所有上層的父節點值都要小於或是大於． 如果題目只給你 tree root，那麼你可以寫出像下面的 function 來檢查這個 tree 是不是 BST.         public bool IsValidBST(TreeNode...

閱讀全文

#26 資料庫基礎 - 存取 Page (Sorted File)

上一篇文章談的內容是針對資料之間是沒有順序的情況，因此在尋找資料時就是採用依照資料的排列順序來尋找．因此整個尋找過程的時間複雜度是 O(n) ．通常來說，資料庫設計者不會讓這樣的事情發生，除非資料本身是一個相當小的參考資料而己，否則資料一旦多了，  O(n) 實在不是一個好現象． 在真實世界中的應用，我們常常可以為資料找到至少一種排列方法，例如，在學校的資料庫中，基本上可以用學生證的號碼來排序學生的資料，因為在同一個學校裡不會有相同的學生證號碼．我們在前面的文章中也提過，一旦資料排序過了之後，時間複雜度就會從 O(n) 下降成 O(log...

閱讀全文

#25 資料庫基礎 - 存取 Page (Heap File)

        在前面的幾篇文章中提到了資料庫引擎讀取與寫入資料時在面對固定長度與非固定長度時所可以採用的儲存方式，其中提供了 Page 為一個儲存空間的管理單位，透過 Page 的機制，讓資料庫引擎能以 Page 為單位做資料讀取與寫入的動作．搭配上 Page 裡的 manifest 資料，資料庫引擎就可以很清楚地知道這個 Page 裡面有多少筆資料以及有多少剩餘空間可用．這時候我們把層次往上拉高一點來看，那 Page 跟 Page 之間的關係是如何定義呢 ? 舉例來說，當某一個表格裡的資料繼續變多時，這些資料很可能會需要很多的...

閱讀全文

#24 我的 IT 人生 - 簡短篇

這一篇內容我不談資料結構，也不談資料庫，更不談寫程式，我來簡單地談一談自己的 IT 人生． 在我還是高中生時，當時有接觸一些電腦課，學會了操作 MS-DOS 系統，也會寫一些簡單的 BASIC 程式，對電腦的確是有相當興趣，但還沒想過要把它當成一生的工作方向．後來，念了大學之後，我念的是機械工程，原本我的打算是想要念電機工程，因為自認為在物理課本中，電學念的比力學好很多，不過也奇怪，我當時還是把機械工程填入到志願卡裡，若我印象沒錯的話，我記得我的志願卡裡還有土木工程電子工程等等相關的工程科系．大學四年就這樣念到畢業了，說實在，到現在我還是覺得大學那 4 年似乎是浪費的，因為我現在沒需要用到任何機械工程的知識．不過，人生就是這樣，現在回過頭來看，就當做是用人生的時間換來了一些人生經驗． 接著，學校畢業後就直接去當兵了．我想這是我整個...

閱讀全文

#23 Coding 面試 Leetcode #73 Set Matrix Zeroes

我打算把以前遇到的一些在面試時遇到的一些特別經驗或感想記錄在這電腦科學筆記裡，一方面，在面試時會遇到的問題大部份都是基礎的電腦科學題目，二方面也把這些過程記錄下來，當做是一種紀念吧! 在美國的軟體行業裡，要做 coding 面試算是很正常的事情，而這些 coding 面試大部份都是資料結構和演算法的內容，所以都是大學的必修課．但其實有許多題目還真的不是光念過課本就能想的到，那些題目還真的需要多練習．在市面上有許多網站會列出一些常見的面試考題，而我之前最常去的網站就是 Leetcode. 這網站不僅記載了許多考題，而且還有 online judge 可以直接測驗你的程式碼是否正確. 今天來聊聊這一題，在 Leetcode 網站上的第 73 題．我被問過一模一樣的題目，面試者連改都沒有改，而這一題也讓我體會到另一種空間複雜度的境界．...

閱讀全文

#22 資料庫的資料實體儲存單位 Page - 3

在來延續上一篇文章 (#21  資料庫的資料實體儲存單位 Page - 2) 的內容．在上一篇的文章中看到了如果沒有 page 的概念時，資料庫引擎有那些可行的方法來在硬碟上管理資料，從上一篇文章中，你看感受到空白空間的處理與以及資料的定位並不是很方便．於是在階層管理的方便性上多加了一層 Page． 在一般市面上常見的資料庫產品中，Page 的大小都大約在幾Kb之間，類似於作業系統的儲存單位大小．所以，一個資料庫可能會包含一個或多個資料庫檔案，而每一個資料庫檔案都會包含多個 Page． 我們再看看如何用 Page 來管理資料．如上一篇文章的情況，資料有可變長度與固定長度兩種．固定長度的情況是比較單純好處理，可以參考下圖: 上圖是某一個...

閱讀全文

#21 資料庫的資料實體儲存單位 Page - 2

延續上一篇文章 (#19 資料庫的資料實體儲存單位 Page) 的內容，在這篇文章裡，我們來談談有關資料庫的實體儲存結構．所謂的實體儲存結構是指資料放在硬碟中的情況． 首先，我們先來看看一個很簡單的結構，資料長度是固定的．這種情況在前面的文章有提過．因為長度都是固定的，所以每筆資料的長度便可以固定，這樣好處是在於方便計算也方便存取． 另一種情況是資料長度不是固定的，這種情況在前面文章也有提過．因為長度不是固定的，因此必須要想一個方法把不同欄位的資料做一個區隔，這樣在讀取資料時才知道什麼情況下是資料欄位的終點．在實體資料儲存時，有兩個方式可以來達成這種目的．第一，在每個資料欄位之間都用一個特殊符號隔開來，長相如下: 上圖是用一個...

閱讀全文

#20 The Power of Ten - 撰寫可靠軟體的思維

標題為 The Power of Ten - Rules for Developing Safety Critical Code 的文章刊登在 IEEE Computer 2006 年 6 月的月刊中，作者是位在 NASA JPL 實驗室的研究科學家，同時也是位學者和工程師．這篇文章可以在 http://spinroot.com/gerard/pdf/P10.pdf 看到． 若以武功修練來比喻的話，這篇文章就像是一個得道高人所寫下來的內功心法，他把自己在 JPL 實驗室工作的多年 C 語言工作心得濃縮成十項重點，作者也為每一個重點留下說明．雖然這一篇文章是將近十年前的文章了，但它的參考價值極高，而且我相信許多資深的軟體工程師幾乎都會同意作者所寫的內容． 其中有幾點並非在所有的程式語言中都會碰的到，尤其是跟記憶體管理有關的工作．以現在一般商業應用裡最常見的...

閱讀全文

#19 資料庫的資料實體儲存單位 Page

在上一篇文章中提到了有關資料庫 Storage manager 一點點的資訊．因此，這一篇文章就來談談更基礎的東西，叫 Page．它是什麼呢 ? 它就是 Storage manager 在處理儲存資料上的一種邏輯格式，也就是每個邏輯儲存空間的大小．這樣說可能還不好了解，讓我來直接舉個例子．資料庫引擎中有一個管理員叫 storage manager，它是負責資料儲存和讀取用，也就是說，今天使用者發出一個請求如 select * from table123，那麼這個命令就會經由資料庫引擎裡各式各樣的管理員來做語法確認解析，來做語法最佳化，然後可能還會經由其他管理員的檢查，最後才會到...

閱讀全文