數(shù)據(jù)庫(kù)基礎(chǔ)知識(shí)

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

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

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

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

5、至少有一個(gè)結(jié)點(diǎn)可以有多于一個(gè)雙親8關(guān)系模型：其數(shù)據(jù)結(jié)構(gòu)是一個(gè)‘二維表框架’組成的集合，每個(gè)二維表稱(chēng)為‘關(guān)系’?；静僮鳎翰迦搿h除、修改、查詢(xún)一、關(guān)系數(shù)據(jù)庫(kù)1基本術(shù)語(yǔ)：關(guān)系元組：表中一行為一個(gè)元組，對(duì)應(yīng)存儲(chǔ)文件中的一個(gè)記錄值屬性：表中的列稱(chēng)為屬性，屬性值相當(dāng)于記錄中的數(shù)據(jù)項(xiàng)或者字段值域：屬性的取值范圍，即不同元組對(duì)同一個(gè)屬性的值所限定的范圍一個(gè)線性表中插入或刪除任何一個(gè)結(jié)點(diǎn)后還是線性結(jié)構(gòu)。2線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱(chēng)為線性鏈表（左指針指向前

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

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

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

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