數(shù)據(jù)庫基礎知識

1、數(shù)據(jù)庫基礎知識1信息系統(tǒng)：一個由人、計算機等組成的能進行信息的收集、傳遞、儲存、加工、維護、分析、計劃、控制、決策和使用的系統(tǒng)。（核心為數(shù)據(jù)庫）2計算機數(shù)據(jù)管理3階段：人工管理階段、文件系統(tǒng)階段、數(shù)據(jù)庫系統(tǒng)階段3數(shù)據(jù)庫系統(tǒng)的組成：數(shù)據(jù)：是信息的符號化，數(shù)據(jù)庫系統(tǒng)的工作對象，數(shù)據(jù)庫數(shù)據(jù)稱為‘存儲數(shù)據(jù)’、‘工作數(shù)據(jù)’或‘操作數(shù)據(jù)’，數(shù)據(jù)庫中的存儲數(shù)據(jù)時‘集成的’‘共享的’。數(shù)據(jù)元素：數(shù)據(jù)的基本單位數(shù)據(jù)對象：性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的

2、一個子集3類用戶：終端用戶—聯(lián)機用戶、最終用戶（從計算機聯(lián)機終端存取數(shù)據(jù)庫的人員）；應用程序員—系統(tǒng)開發(fā)員（負責設計和編制應用程序的人員）；數(shù)據(jù)庫管理員—DBA全面負責數(shù)據(jù)庫系統(tǒng)的管理維護和正常使用的人員。軟件：數(shù)據(jù)庫管理系統(tǒng)DBMSDateBaseManagementSystem硬件——4數(shù)據(jù)庫管理系統(tǒng)：主要功能—數(shù)據(jù)庫定義、數(shù)據(jù)庫存取、數(shù)據(jù)庫運行管理、數(shù)據(jù)庫建立和維護、數(shù)據(jù)通信組成—數(shù)據(jù)定義語言（DDL）、數(shù)據(jù)操縱語言（DML）、數(shù)

3、據(jù)控制語言（DCL）、實用程序5數(shù)據(jù)模型：（1）概念模型：是對客觀事物及其聯(lián)系的抽象，用于信息世界的建模，它強調(diào)其予以表達能力，以及能夠較方便、直接地表達應用中各種語意知識，按用戶的觀點對數(shù)據(jù)和信息建模主要概念——實體、屬性、關鍵字、域、實體型、實體集、聯(lián)系、一對一聯(lián)系、一對多聯(lián)系、多對多聯(lián)系概念模型表示方法：ER圖（實體聯(lián)系法）。主要成分—實體、聯(lián)系、屬性（2）數(shù)據(jù)模型：分為層次、關系、網(wǎng)狀模型，之間的根本區(qū)別在于數(shù)據(jù)之間的聯(lián)系方式不

4、同。關系模型用‘二維表’；層次模型用‘樹結(jié)構’；網(wǎng)狀模型用‘圖結(jié)構’。層次與網(wǎng)狀模型是早期的數(shù)據(jù)模型，稱為格式化數(shù)據(jù)模型6層次模型：最早使用的模型，一棵有向樹。特征：有且僅有一個結(jié)點沒有雙親，為根結(jié)點；其它結(jié)點有且僅有一個雙親每個結(jié)點描述一個實體型，稱為記錄類型；一個記錄類型可以有多個記錄值，簡稱記錄；畫層次模型可用無向邊代替有向邊7網(wǎng)狀模型：兩個或兩個以上的結(jié)點都可以有多個雙親結(jié)點，有向樹變成有向圖特征：可以有一個以上的結(jié)點沒有雙親；

5、至少有一個結(jié)點可以有多于一個雙親8關系模型：其數(shù)據(jù)結(jié)構是一個‘二維表框架’組成的集合，每個二維表稱為‘關系’?；静僮鳎翰迦?、刪除、修改、查詢一、關系數(shù)據(jù)庫1基本術語：關系元組：表中一行為一個元組，對應存儲文件中的一個記錄值屬性：表中的列稱為屬性，屬性值相當于記錄中的數(shù)據(jù)項或者字段值域：屬性的取值范圍，即不同元組對同一個屬性的值所限定的范圍一個線性表中插入或刪除任何一個結(jié)點后還是線性結(jié)構。2線性表的鏈式存儲結(jié)構稱為線性鏈表（左指針指向前

6、件結(jié)點，右指針指向后件結(jié)點稱為雙向鏈表）3帶鏈的棧可以用來收集計算機存儲空間中所有空閑的存儲點稱為可利用棧4鏈式存儲結(jié)構中，存儲數(shù)據(jù)結(jié)構的存儲空間可以不連續(xù)，個數(shù)據(jù)結(jié)點的存儲順序與數(shù)據(jù)元素之間的邏輯關系可以不一致，而數(shù)據(jù)元素之間的邏輯關系式由指針域來確定的四、棧是限定僅在表尾進行插入和刪除操作的線性表。表尾端為棧頂，棧頂元素總是最后被插入的元素，也是最先能被刪除的元素。棧的修改原則：‘先進后出’‘后進先出’棧的順序存儲結(jié)構：Top=0棧

7、空棧的基本運算：入棧（有上溢錯誤）、出棧、讀棧頂元素（棧頂指針不變，棧頂指針為0說明?？?，讀不到棧頂元素）、初始化、置空、判斷棧是佛為空或滿、提取棧頂元素等。五、隊列是限定僅在表的一端進行插入，而在表的另一端刪除數(shù)據(jù)元素的線性表。（先進先出）允許插入的一端——隊尾基本運算：入隊、退隊隊列的順序存儲結(jié)構：循環(huán)隊列，初始狀態(tài)為空六、查找順序查找：在線性表中查找指定的元素二分法查找：只適用于順序存儲的有序表即要求線性表中的結(jié)點必須按照關鍵字值

8、的遞增或遞減順序排列七、樹1一種簡單的非線性結(jié)構，所有數(shù)據(jù)元素之間的關系具有明顯的層次性，是N個結(jié)點的集合2特點：每層平均的結(jié)點數(shù)為樹的度，每一個結(jié)點的度最大為2，當一個結(jié)點既沒有左子樹也沒有右子樹時該結(jié)點為葉子結(jié)點。非空二叉樹只有一個根結(jié)點；每一個結(jié)點最多有兩棵子樹，且分別稱為該結(jié)點的左子樹和右子樹3第K層上最多有2k1（k≥1）個結(jié)點；深度為m的二叉樹最多有2m1個結(jié)點；任意一棵二叉樹，度為0的結(jié)點（葉子結(jié)點）總是比度為2的結(jié)點多一

9、個具有n個結(jié)點的二叉樹，其深度至少為［log2n］14父節(jié)點：每個結(jié)點最多只有一個直接前驅(qū)（前件）根結(jié)點：沒有直接前驅(qū)的結(jié)點只有一個為樹根子結(jié)點：每一個結(jié)點可以有多個后件5滿二叉樹也是完全二叉樹，而完全二叉樹一般不是滿二叉樹前序遍歷：根結(jié)點、左子樹、右子樹中序遍歷：左子樹、根結(jié)點、右子樹后序遍歷：左子樹、右子樹、根結(jié)點八、排序法1冒泡排序法和快速排序法都屬于交換類排序法2冒泡排序法的平均執(zhí)行時間為：n2快速排序法平均執(zhí)行時間為：nlog