YouChen's Blog

B-tree是一種高效的資料結構，特別適用於處理大量資料和優化I/O操作。它常用於多存儲系統中，特別是磁盤存儲和數據庫系統，以確保高效的數據組織和查詢。 磁碟存取資料: 磁碟存取資料的基本過程 根據磁柱號碼使磁頭移動到所需要的柱面上, 這一個過程被稱為定位或是查找 根據磁盤面號來確定指定盤面上的磁道 盤面確定以後, 盤面開始旋轉, 將指定磁區的磁軌段移動至磁頭下 磁碟讀取資料是以block為基本單位的, 因此儘量將相關資訊存放在同一個磁區, 同一磁軌中, 以便在讀寫資料時儘量減少磁頭來回移動的次數, 避免過多的查找時間. 當大量的資料儲存在磁碟中時, 如何高效地查詢磁碟中的資料, 就需要一種合理高效的資料結構了 使用時機 檔案系統或著是資料庫為了增加搜尋的效率, 就可以採用此資料結構. 在資料量變大時, 若用線性搜尋檔案中的紀錄, 效率其實是不好的, 所以這時候就可以建立索引(index), 但資料量又再度增加時, index檔案也會變得很龐大. 為此, 需要一個有效率的搜尋索引, 才能有效率的找到結果. B-Tree 特性 對於一顆m階（階指的是子節點的最大...

Permutation to IndexN 筆資料的所有排列一共 N! 種。 一個階乘進位數字，可以代表一個排列。 Lehmer code 又稱 Cantor expansion ：右方數字個數，階乘，作為數量級。右方較小的、尚未出現的數字個數，作為位數。 1234567891011121314151617181920212223const int N = 5; // 定義陣列長度為 5int a[N] = {4, 1, 5, 2, 3}; // 輸入的排列int c[N+1]; // 樹狀數組，用於計算比當前數字小的數字個數int permutation_to_index() { int fac = 1; // 階乘值，用於計算康托展開 int n = 0; // 最終的索引結果 for (int i=1; i<=N; ++i) { // 計算比...

Binary Heap 為甚麼Binary heap 有兩個特點： Binary heap 是一個完全二元樹 (complete binary tree)，完全樹的意思是除了最後一層外每一層都填滿，最後一層必須由左至右填入。 Max heap 的每個結點的值，大於其左節點的值和右節點的值，根節點是整棵樹最大的節點；Min heap 每個結點的值，小於其左節點的值和右節點的值，根節點是整棵樹最小的節點。

Abstract V.S. Virtual Abstract: An abstract class/method MUST be implemented by derived classes Abstract classes cannot be instantiated directly Classes with abstract methods must be declared abstract Abstract methods have no implementation in the base class Virtual: A virtual method CAN be overridden by derived classes Virtual methods have a default implementation in the base class Classes with virtual methods can be instantiated Derived classes may choose to override or use the bas...

ACID，是指資料庫管理系統（DBMS）在寫入或更新資料的過程中，為保證事務（transaction）是正確可靠的，所必須具備的四個特性：原子性（atomicity，或稱不可分割性）、一致性（consistency）、隔離性（isolation，又稱獨立性，主要針對事務）、持久性（durability）。 在資料庫系統中，一個事務是指：由一系列資料庫操作組成的一個完整的邏輯過程。例如銀行轉帳，從原帳戶扣除金額，以及向目標帳戶添加金額，這兩個資料庫操作的總和，構成一個完整的邏輯過程，不可拆分。這個過程被稱為一個事務，具有 ACID 特性。 資料來源:維基百科 - ACID 四大特性 原子性（Atomicity）：一個事務中的所有操作，需要全部完成，亦或者全部不完成，不會結束在中間某個環節。transaction 在執行過程中發生錯誤，會被 Rollback 到 transaction 開始前的狀態，就像這個事務從來沒有執行過一樣。即，transaction 不可分割、不可約簡。 一致性（Consistency）：在事務開始之前和事務結束以後，資料庫的完整性沒有被破壞。代表寫入的資...

什麼是關聯式資料庫？關聯式資料庫是一組資訊，以預先定義的關係整理資料，可將資料儲存在一或多個資料表 (或「關係」) 的資料欄或資料列中，以輕鬆查看及瞭解不同的資料結構之間有何關聯。「關係」是不同資料表之間的邏輯連結，根據這些資料表之間的互動來建立。 『關聯』是指不同表格中可以通過共同的欄位（通常是主鍵鍵和外鍵）建立關聯。 為什麼我們使用 RDBMS 而不是 noSQLRDBMS 主要的核心在於提供嚴格的 ACID 特性，來確保事務(transaction)的可靠度。這對需要絕對準確性的應用（金融系統、訂單處理 etc…）至關重要。 RDBMS 提供複雜查詢功能，包括多表 JOIN、聚合函數、子查詢等，雖然 noSQL 本身有具備類似的功能，但 noSQL 的 JOIN 效能通常不如 RDBMS，因為 noSQL 設計理念是避免 JOIN RDBMS 中預先定義的 Schema 確保資料格式一致,減少資料品質問題。這在需要嚴格資料規範的企業應用中特別重要。 RDBMS 的設計哲學與核心價值RDBMS 主要圍繞著幾個原則來確保資料的一致性、完整性以及可靠性： ACID 特性 正規化...

什麼是 Redis？Redis 是一種快速、開放原始碼的記憶體內鍵值資料結構存放區。Redis 隨附一組多功能的記憶體內資料結構，讓您能夠輕鬆地建立各種自訂應用程式。Redis 主要使用案例包含快取、工作階段管理、發佈/訂閱以及排行榜。 Redis 位於其他資料庫「之前」，目的是建立一套快取系統，減輕 noSQL or RDB 的負擔，並且加速服務。 ref : https://aws.amazon.com/tw/elasticache/what-is-redis/ 我們該如何使用它？上一段曾說道， Redis 是一套鍵值資料結構存放區，我們可以利用 key 來存放資料，在官方文件有提到 Redis 可以儲存各種位元組序列，包括文字內容、序列化後的物件、計數器數值，以及二進位資料陣列。 以 golang 為例 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707...

二元搜尋法(binary search)用於尋找有序陣列中目標值位置的搜尋演算法。 二元搜尋比較目標值與陣列中間的元素的大小，如果兩者不相等則會捨棄不可能包含目標值那一半區間，然後在剩餘區間重複此過程，每次選取新的中間元素並與目標值比較，直至找到目標或區間為空。若區間為空，則說明目標值不存在。 worst case 狀況時間複雜度為 $O(logn)$，其中 n 為元素數量。 二分搜尋有許多其他形式。例如，分數級聯能加快在多個陣列中尋找同一數值的速度，還能高效地解決計算幾何等領域的搜尋問題；指數搜尋則將搜尋範圍擴充至無界列表。二元搜尋樹和B樹等資料結構的實現也基於二分搜尋原理。 1234567891011121314151617181920212223#include <vector>using namespace std;int binary_search(vector<int>& arr, int target) { int L = 0; int R = arr.size() - 1; while (L &l...

Two Pointer 的產生源自於一個核心問題，如何有效處理陣列或者序列中的配對、區間以及範圍搜尋問題。 最初，我們在遇到需要在陣列中尋找配對或者子陣列的問題時，最直觀的方式便是使用雙重迴圈 (nested loops)。例如，在一個陣列中找到兩個數的和等於目標值： 1234567for(int i = 0; i < arr.len(); i++){ for(int j = i + 1; j < arr.len(); j++){ for(arr[i] + arr[j] == target){ return [i, j]; } }} 但是雙重迴圈的方式，導致的後果就是時間複雜度為 $O(n^2)$ 相比於暴力解法的「盲目搜尋」，Two Pointer 提供了一種「有方向性的搜尋」策略。 兩者差異在於，暴力解需要檢查所有可能組合，two pointer 需要根據問題特性，有策略性的縮小搜尋範圍。 Key PointTwo Pointer 的產生基於對...

Split Array Largest SumProblem DescriptionGiven an integer array nums and an integer k, split nums into k non-empty subarrays such that the largest sum of any subarray is minimized. Return the minimized largest sum of the split. A subarray is a contiguous part of the array. IntuitionThe front element of preorder traversal determines the tree’s root node(the middle of inorder traversal). We use it to determine which element belong to the left subtree or right subtree, and keep comparing the pr...