『壹』 資料庫技術知識數據結構的演算法
資料庫技術知識數據結構的演算法
對於將要參加計算機等級考試的考生來說，計算機等級考試的知識點輔導是非常重要的復習資料。以下是我收集的資料庫技術知識數據結構的演算法，希望大家認真閱讀!
1、數據：數據的基本單位是數據元素。數據元素可由一個或多個數據項組成。數據項是數據的不可分割的最小單位
2、數據結構：數據的邏輯結構、數據的存儲結構、數據的運算
3、主要的數據存儲方式：順序存儲結構(邏輯和物理相鄰，存儲密度大)和鏈式存儲結構
順序存儲結構：
順序存儲計算公式 Li=L0+(i-1)×K 順序結構可以進行隨機存取;插人、刪除運算會引起相應節點的大量移動
鏈式存儲結構：a、指針域可以有多個，可以指向空，比比順序存儲結構的存儲密度小
b、邏輯上相鄰的節點物理上不一定相鄰。 c、插人、刪除等不需要大量移動節點
4、順序表：一般情況下，若長度為n的順序表，在任何位置插入或刪除的概率相等，元素移動的平均次數為n/2(插入)和(n-1)/2(刪除)。
5、鏈表：線性鏈表(單鏈表和雙向鏈表等等)和非線性鏈表
線性鏈表也稱為單鏈表，其每個一節點中只包含一個指針域，雙鏈表中，每個節點中設置有兩個指針域。(注意結點的插入和刪除操作)
6、棧：“後進先出”(LIFO)表。棧的應用：表達式求解、二叉樹對稱序周遊、快速排序演算法、遞歸過程的實現等
7、隊列：“先進先出”線性表。應用：樹的層次遍歷
8、串：由零個或多個字元組成的有限序列。
9、多維數組的順序存儲：
10、稀疏矩陣的存儲：下三角矩陣順序存儲
其他常見的存儲方法還有三元組法和十字鏈表法
11、廣義表：由零個或多個單元素或子表所組成的有限序列。廣義表的元素可以是子表，而子表的元素還可以是子表
12、樹型結構：非線性結構。常用的樹型結構有樹和二叉樹。
二叉樹與樹的區別：二叉樹不是樹的特殊情況，樹和二叉樹之間最主要的區別是：二叉樹的節點的子樹要區分左子樹和右子樹，即使在節點只有一棵子樹的情況下也要明確指出該子樹是左子樹還是右子樹。
13、樹(森林)與二叉樹之間的轉換(要會轉換)
14、二叉樹和樹的周遊(遍歷)
二叉樹的周遊主要有以下3種方式：前序法(NLR)、對稱序法(LNR)、後序法(LRN)
周遊樹和樹林：深度優先和按廣度優先兩種方式進行。深度優先方式又可分為按先根次序和按後根次序周遊
樹與二叉樹周遊之間的對應關系：按先根次序周遊樹正好與按前序法周遊樹對應的二叉樹等同，後根次序周遊樹正好與按對稱序法周遊對應的`二叉樹等同
按廣度優先方式就是層次次序周遊
15、二叉樹的存儲和線索
二叉樹的存儲結構：二叉樹的llink一rlink法存儲表示
線索二叉樹：在有n個節點的二叉樹的且llink - rlink法存儲表示中，必定有n+1個空指針域
16、哈夫曼樹：一類帶權路徑長度最短的樹。樹的帶權路徑長度為樹中所有葉子節點的帶權路徑長度之和WPL。
17、查找：
(1)順序查找：平均查找長度為(n +1 )/2次，時間復雜度為O(n)
(2)二分法查找：線性表節點必須按關鍵碼值排序，且線性表是以順序存儲方式存儲的。查找成功比較次數log2n，查找失敗比較次數log2n+1
(3)分塊查找：先是塊間查找，然後塊內查找。
(4)散列表(哈希表Hash)的存儲和查找：處理沖突的方法：開地址法(線性探測法)、拉鏈法等
負載因子(裝填因子)=表實際存儲的結點個數/表的最大能存儲結點個數(即表長)
二叉排序樹：每個結點左子樹的所有關鍵碼值都小於該結點關鍵碼值，右子樹所有結點關鍵碼值都大於該結點關鍵碼值。對稱周遊二叉排序樹，得到一個有序序列，時間復雜度O(log2n)
B樹和B+樹：M階樹，每個結點至多有M-1個關鍵碼，至少有M/2(取上界)-1個關鍵碼。B樹適合隨機查找，不適合順序查找。B+樹適合順序查找。
18、排序
直接插人排序、希爾排序、直接選擇排序、堆排序、起泡排序、快速排序等排序演算法要了解。
直接選擇排序、希爾排序、快速排序和堆排序是不穩定排序，其他排序為穩定排序
;『貳』 什麼是拉鏈表
拉鏈表，記錄每條信息的生命周期，一旦一條記錄的生命周期結束，就重新開始一條新的記錄，並把當前日期放入生效開始日期。
如果當前信息至今有效，在生效結束日期中填入一個極大值( 如 9999-99-99 )。
拉鏈表適合於：數據會發生變化，但是大部分是不變的。（即：緩慢變化維）
比如：用戶信息會發生變化，但是每天變化的比例不高。如果數據量有一定的規模，按照每日全量的方式保存效率很低。
通過，生效開始日期<=某個日期 且 生效結束日期>=某個日期，能夠得到某個時間點的數據全量切片
『叄』 我的Myqls資料庫中有2個數據表，每個數據表都有超過3千萬條記錄，查詢效率很低，有沒有什麽好的辦法優化
首先換資料庫，Mysql處理這個數量級數據比較吃力。推薦你用DB2 或ORACLE
如果不能換，檢查一下存儲引擎用InnoDB，如果是，檢查
innodb_flush_log_at_trx_commit 這個選項，是否是1
如果是1 用SET AUTOCOMMIT = 0 ，提高數據修改速度
PHP優化需要
MySQL Slow Log 分析工具分析日誌：mysqlmpslow或mysqlsla比較不錯。
Explain/ DESC 分析SQL 的執行情況和SHOW PROCESSLIST
使用SHOW PROCESSLIST 看是否有鎖表情況，
設置 my.cnf 中的long-query-time 和log-slow-queries 記錄伺服器那些SQL執行速度比較慢
根據上述情況查看對對應的SQL語句進行優化
優化伺服器性能，用RAID5（SAN），加內存本身的升級，提高硬碟I/O性能。
資料庫總體性能優化：
數據表最好能拆成小表。
資料庫切片，分到不用的伺服器上，
資料庫訪問性能優化
修改my.cnf, 下面是影響比較大的：
innodb_flush_log_at_trx_commit 設置為0
如果比下面值大就不用調整了：
query_cache_size 設置為16M
sort_buffer_size 設置為16M
record_buffer 設置為16M
key_buffer_size 設置為8M
innodb_buffer_pool_size 設置為32M
下面是建議設置的
table_cache 設置為512
read_buffer_size 設置為16M
myisam_sort_buffer_size設置為16M
innodb_additional_mem_pool_size 設置為128M
innodb_log_file_size 設置為256M
innodb_log_buffer_size設置為8M
資料庫表優化，
1 建立相應的INDEX
2 統一編碼，MySQL的默認編碼是Latin1，不支持中文，需要把資料庫的默認編碼修改為gbk或者utf8
show variables like 'character%' 查看
另外表的編碼也要與資料庫統一
『肆』 OLTP和OLAP有何區別
1、適用人員不同：OLTP主要供基層人員使用，進行一線業務操作。OLAP則是探索並挖掘數據價值，作為企業高層進行決策的參考。
2、面向內容不同：OLTP面向應用，OLAP面向主題；
4、數據特點不同：OLTP的數據特點是當前的、最新的、細節的, 二維的、分立的；而OLTP則是歷史的, 聚集的, 多維的，集成的, 統一的；
5、存取能力不同：OLTP可以讀/寫數十條記錄，而OLAP則可以讀上百萬條記錄；
6、工作事件的復雜度不同：OLTP執行的是簡單的事務，而OLAP執行的是復雜任務；
7、可承載用戶數量不同：OLTP的可承載用戶數量為上千個，而OLAP則是上百萬個；
8、DB大小不同：OLTP的DB 大小為100GB，而OLAP則可以達到100TB；
9、執行時間要求不同：OLTP具有實時性，OLAP對時間的要求不嚴格。
(4)資料庫拉鏈切片擴展閱讀：
OLTP與OLAP的實際應用
OLAP工具是針對特定問題的聯機數據訪問與分析。它通過多維的方式對數據進行分析、查詢和報表。維是人們觀察數據的特定角度。
例如，一個企業在考慮產品的銷售情況時，通常從時間、地區和產品的不同角度來深入觀察產品的銷售情況。這里的時間、地區和產品就是維。
這些維的不同組合和所考察的度量指標構成的多維數組則是OLAP分析的基礎，可形式化表示為（維1，維2，……，維n，度量指標），如（地區、時間、產品、銷售額）。
多維分析是指對以多維形式組織起來的數據採取切片（Slice）、切塊（Dice）、鑽取（Drill-down和Roll-up）、旋轉（Pivot）等各種分析動作，以求剖析數據，使用戶能從多個角度、多側面地觀察資料庫中的數據，從而深入理解包含在數據中的信息。
應用OLTP，就必須重新定義OLTP在企業信息化體系結構中的地位。OLTP不再只是一套能處理訂單的老式應用程序。對典型的OLTP系統處理的大規模數據流更新進行同時分析，這種情況很罕見，因為一般認為這不是OLTP的目的。
數據倉庫更新固有的延遲阻礙著對最新數據的近實時分析。組織如果要對於數據的變化迅速作出反應，IT部門就必須讓OLTP產生比以往更大的作用。
參考資料來源：網路-OLTP
參考資料來源：網路-聯機分析處理
『伍』 什麼叫「上鑽」、「下鑽」、「切片」和「轉軸」這是屬於資料庫哪一章的內容
上鑽：從當前數據往上回歸到上一層數據。例如：（某數據的分類下面分為品名）從品名列表收攏到分類列表。
下鑽：從當前數據往下展開下一層數據。例如：（某數據的分類下面分為品名）從分類列表展開到品名列表。
上鑽、下鑽統稱鑽取。
切片：展現同一層面的數據。如上述的產品。
轉軸：這些應該屬於查詢、展現范疇。
原材料
標準的馬氏體不銹鋼是：403、410、414、416、416(Se)、420、431、440A、440B和440C型，這些鋼材的耐腐蝕性來自「鉻」，其范圍是從11.5至18%，鉻含量愈高的鋼材需碳含量愈高，以確保在熱處理期間馬氏體的形成，上述三種440型不銹鋼很少被考慮做為需要焊接的應用，且440型成份的熔填金屬不易取得。
以上內容參考：網路-轉軸