golang - 有哪些设计数据结构方面的小技巧(奇技淫巧)？

Question

传奇的软件工程师Frederick P. Brooks曾经说过：“给我看你的数据”。因此可见数据结构对于一个程序来说是多么的重要，如果你不了解程序中的数据结构，你根本就无法去理解整个程序

有哪些设计数据结构方面的小技巧？

Answer 1

寫在前面的話：總是在災難發生後，才想起容災的重要性；總是在吃過虧後，才記得有人提醒過

本文主要是針對mysql資料庫

設計原則

1、不在資料庫做運算：cpu計算務必移至業務層
2、控制單表資料量：單表記錄控制在1000w
3、控制列數量：字段數控制在20以內
4、平衡範式與冗餘餘：為提高效率犧牲範式設計，冗餘資料
5、拒絕3B：拒絕大sql，大事務，大批量
6、表字符集使用UTF8
7、使用INNODB存儲引擎

資料表設計

1、盡可能使用最有效(最小)的資料型別

tinyint(1Byte)
smallint(2Byte)
mediumint(3Byte)
int(4Byte)
bigint(8Byte)
bad case：int(1)/int(11)

2、不要將數字儲存為字串，字元轉換為數字，用int儲存ip而非char(15)
3、優先使用enum或set，sex enum ('F', 'M')
4，避免使用NULL欄位

NULL字段很难查询优化
NULL字段的索引需要额外空间
NULL字段的复合索引无效
bad case：`name` char(32) default null`age` int not null
good case：`age` int not null default 0

5，少用text/blob，varchar的效能會比text高很多；實在避免不了blob，請拆表
6、不在資料庫裡存圖片
7、對於MyISAM表，如果沒有任何變長列(VARCHAR、 TEXT或BLOB列)，使用固定尺寸的記錄格式。這比較快但是不幸地可能會浪費一些空間。即使你已經用CREATE選項讓VARCHAR列ROW_FORMAT=fixed，也可以提示想使用固定長度的行
8、使用sample character set，例如latin1。盡量少使用utf-8，因為utf-8佔用的空間是latin1的3倍。可以在不需要使用utf-8的欄位上面使用latin1，例如mail，url等
9、精確度與空間的轉換。在儲存相同數值範圍的資料時，浮點數類型通常都會比DECIMAL類型使用更少的空間。 FLOAT欄位使用4 位元組儲存 資料。 DOUBLE類型需要8 個位元組並擁有更高的精確度和更大的數值範圍，DECIMAL類型的資料將會轉換成DOUBLE類型
10、庫名表名字段名必須有固定的命名長度，12個字元以內；庫名、表名、字段名禁⽌止超過32個字元。須見名之意；庫名、表名、字段名禁⽌止使⽤用MySQL保留字；臨時庫、表名必須以tmp為前綴，並以⽇日期為後綴；備份庫、表必須以bak為前綴，並以日期為後綴
11、InnoDB表格行記錄物理長度不超過8KB，InnoDB的data page預設是16KB，基於B+Tree的特點，一個data page中需要至少儲存2筆記錄。因此，當實際儲存長度超過8KB（尤其是TEXT/BLOB列）的大列（large column）時會引起“page-overflow儲存”，類似ORACLE中的“行遷移”，因此，如果必須使用大列（尤其是TEXT/BLOB類型）且讀寫頻繁的話，則最好把這些列拆分到子表中，不要和主表放在一起存儲，如果不太頻繁，可以考慮繼續保留在主表中，如果將innodbpagesize 選項修改成8KB，那麼行記錄實體長度建議不超過4KB

索引類

1、謹慎合理使用索引

改善查询、减慢更新
索引一定不是越多越好（能不加就不加，要加的一定得加）
覆盖记录条数过多不适合建索引，例如“性别”

2、字元欄位必須建立前綴索引
3、不在索引做列運算，bad case：select id where age +1 = 10;
4、innodb主鍵推薦使用自增列

主键建立聚簇索引
主键不应该被修改
字符串不应该做主键
如果不指定主键，innodb会使用唯一且非空值索引代替

5、不用外鍵，請由程式保證約束
6、避免在已有索引的前綴上建立索引。例如：如果存在index（a，b）則去掉index（a）
7、控制單一索引的長度。使用key（name（8））在資料的前面幾個字元建立索引
8、要選擇性的使用索引。在變化很少的列上使用索引並不是很好，例如性別列
9、Optimize table可以壓縮和排序index，注意不要頻繁運行
10、Analyze table可以更新資料
11、索引選擇性是不重複的索引值也叫基數（cardinality）表中資料行數的比值，索引選擇性=基數/資料行，count(distinct(username))/count(*) 是索引選擇性，高索引選擇性的好處就是mysql尋找符合的時候可以過濾更多的行，唯一索引的選擇性最佳，值為1
12、不要用重複或多餘索引，對於INNODB引擎的索引來說，每次修改資料都要把主鍵索引，輔助索引中對應索引值修改，這可能會出現大量資料遷移，分頁，以及碎片的出現
13、超過20個長度的字串列，最好建立前綴索引而非整列索引（例如：ALTER TABLE t1 ADD INDEX(user(20))），可以有效提高索引利用率，不過它的缺點是對這個列排序時用不到前綴索引。前綴索引的長度可以基於對該字段的統計得出， 一般略大於平均長度一點就可以了
14、定期用 pt-duplicate-key-checker 工具檢查並刪除重複的索引。例如 index idx1(a, b) 索引已經涵蓋了 index idx2(a)，就可以刪除 idx2 索引了

sql語句設計類別

1、sql語句盡可能簡單,一條sql只能在一個cpu運算，大語句拆小語句，減少鎖時間，一條大sql可以堵死整個庫(充分利用QUERY CACHE和充分利用多核CPU)
2、簡單的事務,事務時間盡可能短,bad case：上傳圖片事務
3、避免使用trig/func,觸發器、函數不用,客戶端程序取而代之
4、不用select *,消耗cpu，io，內存，頻寬,這種程式不具有擴充性
5、OR改寫為IN()

or的效率是n级别
in的消息时log(n)级别
in的个数建议控制在200以内
select id from t where phone=’159′ or phone=’136′ =>select id from t where phone in (’159′, ’136′);

6、OR改寫為UNION

mysql的索引合併很弱智

select id from t where phone = '159' or name = 'john';
=>
select id from t where phone='159' union  select id from t where name='jonh';

7、避免負向%，如not in/like
8、慎用count(*)
9、limit高效分頁

limit越大，效率越低

select id from t limit 10000, 10;
=>
select id from t where id > 10000 limit 10;

10、使用union all替代union，union有去重開銷
11、少用連接join
12、使用group by，分組、自動排序
13、請使用同型別比較
14、使用load data導數據，load data比insert快約20倍；
15、對資料的更新要打散後批次更新，不要一次更新太多資料
16、使用效能分析工具

Sql explain  /  showprofile   /    mysqlsla

17、使用--log-slow-queries –long-query-time=2查看查詢比較慢的語句。再使用explain分析查詢，做出最佳化

show profile;
mysqlsla;
mysqldumpslow;
explain;
show slow log;
show processlist;
show query_response_time(percona)

optimize 資料在插入，更新，刪除的時候難免一些資料遷移，分頁，之後就出現一些碎片，久而久之碎片累積起來影響效能， 這就需要DBA定期的最佳化資料庫減少碎片，這就透過optimize指令。如對MyISAM表操作：optimize table 表名

18、禁止在資料庫中跑大查詢
19、使⽤預編譯語句，只傳參數，比傳遞SQL語句更有效率；一次解析，多次使用；降低SQL注入機率
20、禁止使⽤order by rand ()
21、禁⽌單條SQL語句同時更新多個表
22、避免在資料庫中進⾏數學運算(MySQL不擅長數學運算和邏輯判斷)
23、SQL語句要求所有研發，SQL關鍵字全部是大寫，每個字只允許有一個空格
24、能不用NOT IN就不用NOTIN，坑太多了。 。會把空和NULL給查出來

注意

1、即使是基於索引的條件過濾，如果優化器意識到總共需要掃描的資料量超過30%時（ORACLE裡貌似是20%，MySQL目前是30%，沒準以後會調整），就會直接改變執行計劃為全表掃描，不再使用索引
2、多表JOIN時，要把過濾性最大（不一定是數據量最小哦，而是只加了WHERE條件後過濾性最大的那個）的表選為驅動表。此外，如果JOIN之後有排序，排序欄位一定要屬於驅動表，才能利用驅動表上的索引完成排序
3、絕大多數情況下，排序的代價通常要來的更高，因此如果看到執行計劃中有Using filesort，優先建立排序索引吧
4、利用pt-query-digest 定期分析slow query log，並結合Box Anemometer 建置slow query log分析及最佳化系統

Answer 2

今天看到一些比較有趣的東西：
Which algorithms/data structures should I “recognize” and know by name?