一、查找?
靜態(tài)查找
無序查找：一個個對比O(n)
順序查找：二分查找法蜈项，O(logn)〗某模可通過將查找過程建立二叉判定樹來計算時間復(fù)雜度，查找到一個元素的過程實際上就是從根節(jié)點找到目標(biāo)節(jié)點的過程轴总，比較次數(shù)即為樹的深度，而根據(jù)二叉樹的性質(zhì)际乘，深度為k的二叉樹的結(jié)點總數(shù)為2的k次冪再-1漂佩，所以n各節(jié)點的樹的深度為log(n+1)，所以時間復(fù)雜度即為深度O(logn)养葵。
動態(tài)查找
1 ?二叉排序樹/搜索樹
是一棵左結(jié)點比根根節(jié)點小瘩缆，右結(jié)點比根結(jié)點大的樹，遞歸定義庸娱，并允許樹/子樹為空。
時間復(fù)雜度與二叉判定樹算法一樣归露，但上面的深度計算公式是完全二叉樹的情況斤儿，二叉搜索樹在最壞的情況下可能是一棵單鏈的樹，時間復(fù)雜度為O(n)疆液。一般情況下大約占40%多陕贮，時間復(fù)雜度還是O(logn)。所以不穩(wěn)定飘蚯。
2 ?二叉平衡樹
由于二叉排序樹時間復(fù)雜度的不穩(wěn)定福也，就引入了平衡的概念，使左右子樹高度之差保持在1內(nèi)峦甩。插入和刪除樹都需要嚴(yán)格維持平衡狀態(tài)進(jìn)行大量旋轉(zhuǎn)。
?1）紅黑樹：
? ? 紅黑樹是一棵不“完全平衡”的平衡樹凯傲，借助紅黑樹的五個性質(zhì)冰单，能保證其時間復(fù)雜度在O(logn)。
? ? 與平衡二叉樹相比诫欠，其插入時的旋轉(zhuǎn)操作與AVL一樣都能維持在兩個旋轉(zhuǎn)內(nèi)，刪除比AVL穩(wěn)定轿偎，紅黑樹能保證在刪除時旋轉(zhuǎn)操作最多三次被廓，而AVL有可能會導(dǎo)致被刪節(jié)點到根節(jié)點都需要旋轉(zhuǎn)，O(logn)昆婿。
? ? 5個性質(zhì)：a.節(jié)點非黑即紅 b.根節(jié)點是黑色 c.所有Null成為葉子結(jié)點蜓斧，也是黑色 ?d.所有紅節(jié)點的子節(jié)點都是黑色的（不可能兩個紅的相連）e.任一節(jié)點到其葉子結(jié)點的所有路徑上的黑節(jié)點數(shù)量相同，（最短路徑==最長路徑法精，平衡所在）
2）B樹 B+樹
平衡的多路查找樹
二、索引
1.為啥不用平衡二叉樹或紅黑樹狼荞？
索引是為了加快查詢的速度的一種方式帮碰，索引一般都很大，因此不可能將其放在內(nèi)存中丰涉，一般也是放在磁盤上斯碌。所以，在選取索引的數(shù)據(jù)結(jié)構(gòu)時傻唾，要考慮的更多的是訪問磁盤的I/O次數(shù)承耿。
在樹形結(jié)構(gòu)中加袋，我們訪問一個節(jié)點就要做一次I/O操作抱既，即樹的深度就是我們做I/O操作的次數(shù)。而其他的樹都是二叉樹防泵，無形中就限制了樹的高度。所以我們采用m階的B樹（不是m叉樹Ｌ褡堋６切稀）實現(xiàn)，B樹比一般的二叉樹更加矮胖贱纠，符合我們的要求响蕴。
2.為啥用B+不用B樹？
B樹和B+樹都是很矮胖的樹浦夷。結(jié)構(gòu)上有所不同
1）B樹
B樹滿足幾個性質(zhì)：a.每個節(jié)點最多有m個子樹劈狐，b.根節(jié)點最少兩個或為葉子結(jié)點，c.其他節(jié)點最多ceil(m/2)個子樹 d.任何一個節(jié)點都包含一個其0上關(guān)鍵字的數(shù)量肥缔，關(guān)鍵字和和指向子樹的指針（交替），關(guān)鍵字順序排序（搜索樹案耐А）坟岔。e.所有葉子結(jié)點都在同一層上，不帶任何信息炮车。（可用來說明查找失斒菽隆）
B樹的每個節(jié)點包含最少ceil(m/2)個關(guān)鍵字以及指針（數(shù)量一致o），就是他的每個節(jié)點都是包含數(shù)據(jù)信息的扛或，他的所有葉子結(jié)點都沒有信息。
每次查找到一個節(jié)點需要做兩個操作悲伶，（1）去磁盤讀取數(shù)據(jù)（一個節(jié)點上ceil（m/2）） （2）在讀取的幾個數(shù)據(jù)中查找要找的數(shù)據(jù)住涉。由于B樹節(jié)點分支較二叉樹多而矮胖，所以只需要少數(shù)的幾次I/O操作即可花沉。時間復(fù)雜度是O（log以ceil(m/2)為底 N）
2）B+樹
B+樹與B樹有幾個區(qū)別媳握，首先B+ 樹每個節(jié)點上只有關(guān)鍵字，我們可以將它看作索引娩脾，并且含有n個子樹的節(jié)點上有n個關(guān)鍵字打毛。葉子節(jié)點上包含所有信息以及指向含這些信息的指針，并且葉子結(jié)點之間依關(guān)鍵字大小順序鏈接幻枉。
由此我們可以推出展辞，B+樹由于B樹的幾個地方。
????a.B樹每個節(jié)點包含信息多罗珍，占空間大，導(dǎo)致整個索引在磁盤中占的空間會比B+樹的大蘸朋，當(dāng)我們要加載索引進(jìn)內(nèi)存時扣唱，B+樹就能加載的更多（一個盤快上存的更多）团南，一次I/O操作能做更多的查詢炼彪。
????b.由于B+樹的葉子結(jié)點包含全部信息且按順序相連，當(dāng)有范圍查找時拷橘，B+樹就不需要多次讀寫內(nèi)存了喜爷，而B樹要遍歷樹
? ? c.B+樹的查詢更加穩(wěn)定，都是在葉子節(jié)點上术幔，比較次數(shù)每次都一樣湃密。
3 hash索引
hash索引即利用哈希表將key映射在哈希表上，沖突采用鏈地址法勾缭。（like hashmap結(jié)構(gòu) ）
所以哈希索引查找速度非沉┯桑快了O(1)，但十分局限幻梯，只適用于等值查詢較多，且重復(fù)元素較少的情況（避免沖突 鏈表過長）咬摇。
三煞躬、數(shù)據(jù)庫優(yōu)化
1）數(shù)據(jù)庫設(shè)計方面
建立索引-->在SQL方面就避免使用會使索引失效的語句，比如控制查詢在扰，不等雷客，計算操作等。
盡量使用固定長度的字段（提高性能皱卓，可直接計算出偏移量），
限制字段長度（存放在磁盤中占用空間小娜汁，可一次多讀取一些）存炮，
分區(qū)（將數(shù)據(jù)存儲在不同磁盤蜈漓，查找去對應(yīng)磁盤找，表還是一個表）融虽、主從，分表分庫
2）數(shù)據(jù)庫I/O方面
增加緩沖區(qū)般又、
若涉及表的的級聯(lián)巍佑，將不同的表存儲在不同的磁盤上，以增加I/O速度堕义。（并行讀取嗎脆栋？？怕膛？不懂）
3）SQL語句方面
關(guān)聯(lián)時小表為主表秦踪、查詢時篩選多的條件在前，避免select*,需要什么查什么等
限制反悔的條目數(shù)柠逞，使用分頁
4）Java方面
PrepareStatement希坚，預(yù)處理緩存
存儲過程，預(yù)處理裁僧，緩存慕购，速度快沪悲，重復(fù)代碼少（不好維護(hù)）
存儲過程的優(yōu)缺點：
優(yōu)點：a.復(fù)雜業(yè)務(wù)邏輯封裝阱表，復(fù)用
? ? ? ? ? ?b.將多條sql訪問數(shù)據(jù)庫的操作合并為一條
? ? ? ? ? ? c.只編譯一次殿如，不需要每次都重新編譯
? ? ? ? ? ? d.可設(shè)置用戶權(quán)限最爬，安全性高
缺點：a.不易調(diào)試 ，難以維護(hù)烤送，難修改
? ? ? ? ? ? b.可移植性差糠悯，不同數(shù)據(jù)庫寫存儲過程語法有不同
PrepareStatement 和 Statement區(qū)別
執(zhí)行靜態(tài)的Sql語句，即完整的語句互艾；prepareStatement可以包含動態(tài)參數(shù)“纫普？”，預(yù)防SQL注入
statement每次都需要編譯執(zhí)行局嘁；prepareStatement會進(jìn)行預(yù)編譯悦昵，將命令放在緩沖區(qū)中，下次執(zhí)行時就不需要在編譯了但指，大大提高效率（jdbc存儲過程）
prepareStatement支持批處理
SQL注入
SQL注入：攻擊者將SQL命令通過表單輸入框或頁面請求查詢字符串插入后臺執(zhí)行SQL中棋凳，欺騙服務(wù)器執(zhí)行惡意SQL命令的（一般使用or 1==1）
防范：a.檢查數(shù)據(jù)變量類型和格式
? ? ? ? ? ?b.過濾特殊符號
? ? ? ? ? ? c.綁定變量，使用預(yù)編譯語句
????????????d.判斷返回數(shù)據(jù)的條數(shù)
