Äú¿ÉÒÔ¾èÖú£¬Ö§³ÖÎÒÃǵĹ«ÒæÊÂÒµ¡£

1Ôª 10Ôª 50Ôª





ÈÏÖ¤Â룺  ÑéÖ¤Âë,¿´²»Çå³þ?Çëµã»÷Ë¢ÐÂÑéÖ¤Âë ±ØÌî



  ÇóÖª ÎÄÕ ÎÄ¿â Lib ÊÓÆµ iPerson ¿Î³Ì ÈÏÖ¤ ×Éѯ ¹¤¾ß ½²×ù Model Center   Code  
»áÔ±   
   
 
     
   
 ¶©ÔÄ
  ¾èÖú
Ò»ÎÄ¿´¶®Êý¾Ý¿âÔ­Àí
 
  6007  次浏览      27
 2019-8-27
 
±à¼­ÍƼö:
±¾ÎÄÀ´×ÔÓÚcsdn£¬±¾ÎÄÖ÷Òª½éÉÜÁËÊý¾Ý¿âÖеÄB+Ê÷Ë÷Òý¸ÅÊö£¬ Êý¾Ý¿âµÄÈ«¾Ö¸ÅÊö£¬ »ùÓڳɱ¾µÄÓÅ»¯¸ÅÊö£¬ÌرðרעÁËÁª½ÓÔËË㣬 »º³å³Ø¹ÜÀí¸ÅÊö£¬ ÊÂÎñ¹ÜÀí¸ÅÊöµÈÏà¹ØÖªÊ¶¡£

Ò»Ìáµ½¹ØÏµÐÍÊý¾Ý¿â£¬ÎÒ½û²»×¡Ï룺ÓÐЩ¶«Î÷±»ºöÊÓÁË¡£¹ØÏµÐÍÊý¾Ý¿âÎÞ´¦²»ÔÚ£¬¶øÇÒÖÖÀà·±¶à£¬´ÓСÇÉʵÓÃµÄ SQLite µ½Ç¿´óµÄ Teradata ¡£µ«ºÜÉÙÓÐÎÄÕ½²½âÊý¾Ý¿âÊÇÈçºÎ¹¤×÷µÄ¡£Äã¿ÉÒÔ×Ô¼º¹È¸è/°Ù¶Èһϡº¹ØÏµÐÍÊý¾Ý¿âÔ­Àí¡»£¬¿´¿´½á¹û¶àôµÄÏ¡ÉÙ¡¾ÒëÕß×¢£º°Ù¶ÈΪÄúÕÒµ½Ïà¹Ø½á¹ûÔ¼1,850,000¸ö¡­¡¿ £¬¶øÇÒÕÒµ½µÄÄÇЩÎÄÕ¶¼ºÜ¶Ì¡£ÏÖÔÚÈç¹ûÄã²éÕÒ×î½üʱ÷ֵļ¼Êõ£¨´óÊý¾Ý¡¢NoSQL»òJavaScript£©£¬ÄãÄÜÕÒµ½¸ü¶àÉîÈë̽ÌÖËüÃÇÈçºÎ¹¤×÷µÄÎÄÕ¡£

ÄѵÀ¹ØÏµÐÍÊý¾Ý¿âÒѾ­Ì«¹ÅÀÏÌ«ÎÞȤ£¬³ýÁË´óѧ½Ì²Ä¡¢Ñо¿ÎÄÏ׺ÍÊé¼®ÒÔÍ⣬ûÈËÔ¸Òâ½²ÁËÂð£¿

×÷Ϊһ¸ö¿ª·¢ÈËÔ±£¬ÎÒ²»Ï²»¶ÓÃÎÒ²»Ã÷°×µÄ¶«Î÷¡£¶øÇÒ£¬Êý¾Ý¿âÒѾ­Ê¹ÓÃÁË40ÄêÖ®¾Ã£¬Ò»¶¨ÓÐÀíÓɵġ£¶àÄêÒÔÀ´£¬ÎÒ»¨Á˳ɰÙÉÏǧ¸öСʱÀ´ÕæÕýÁì»áÕâЩÎÒÿÌì¶¼ÔÚÓõġ¢¹Å¹ÖµÄºÚºÐ×Ó¡£¹ØÏµÐÍÊý¾Ý¿â·Ç³£ÓÐȤ£¬ÒòΪËüÃÇÊÇ»ùÓÚʵÓöøÇҿɸ´ÓõĸÅÄî¡£Èç¹ûÄã¶ÔÁ˽âÒ»¸öÊý¾Ý¿â¸ÐÐËȤ£¬µ«ÊÇ´ÓδÓÐʱ¼ä»òÒâÔ¸À´¿Ì¿à×êÑÐÕâ¸öÄÚÈݹ㷺µÄ¿ÎÌ⣬ÄãÓ¦¸Ãϲ»¶ÕâÆªÎÄÕ¡£

ËäÈ»±¾ÎıêÌâºÜÃ÷È·£¬µ«ÎÒµÄÄ¿µÄ²¢²»Êǽ²ÈçºÎʹÓÃÊý¾Ý¿â¡£Òò´Ë£¬ÄãÓ¦¸ÃÒѾ­ÕÆÎÕÔõôдһ¸ö¼òµ¥µÄ join query£¨Áª½Ó²éѯ£©ºÍCRUD²Ù×÷£¨´´½¨¶ÁÈ¡¸üÐÂɾ³ý£©£¬·ñÔòÄã¿ÉÄÜÎÞ·¨Àí½â±¾ÎÄ¡£ÕâÊÇΨһÐèÒªÄãÁ˽âµÄ£¬ÆäËûµÄÓÉÎÒÀ´½²½â¡£

ÎÒ»á´ÓһЩ¼ÆËã»ú¿ÆÑ§·½ÃæµÄ֪ʶ̸Æð£¬±ÈÈçʱ¼ä¸´ÔÓ¶È¡£ÎÒÖªµÀÓÐЩÈËÌÖÑáÕâ¸ö¸ÅÄµ«ÊÇûÓÐËüÄã¾Í²»ÄÜÀí½âÊý¾Ý¿âÄÚ²¿µÄÇÉÃîÖ®´¦¡£ÓÉÓÚÕâÊǸöºÜ´óµÄ»°Ì⣬ÎÒ½«¼¯ÖÐ̽ÌÖÎÒÈÏΪ±ØÒªµÄÄÚÈÝ£ºÊý¾Ý¿â´¦ÀíSQL²éѯµÄ·½Ê½¡£ÎÒ½ö½ö½éÉÜÊý¾Ý¿â±³ºóµÄ»ù±¾¸ÅÄÒÔ±ãÔÚ¶ÁÍê±¾ÎĺóÄã»á¶Ôµ×²ãµ½µ×·¢ÉúÁËʲôÓиöºÜºÃµÄÁ˽⡣

¡¾ÒëÕß×¢£º¹ØÓÚʱ¼ä¸´ÔÓ¶È¡£¼ÆËã»ú¿ÆÑ§ÖУ¬Ëã·¨µÄʱ¼ä¸´ÔÓ¶ÈÊÇÒ»¸öº¯Êý£¬Ëü¶¨Á¿ÃèÊöÁ˸ÃËã·¨µÄÔËÐÐʱ¼ä¡£Èç¹û²»Á˽âÕâ¸ö¸ÅÄÒéÏÈ¿´¿´Î¬»ù»ò°Ù¶È°Ù¿Æ£¬¶ÔÓÚÀí½âÎÄÕÂÏÂÃæµÄÄÚÈݺÜÓаïÖú¡¿

ÓÉÓÚ±¾ÎÄÊǸö³¤Æª¼¼ÊõÎÄÕ£¬Éæ¼°µ½ºÜ¶àËã·¨ºÍÊý¾Ý½á¹¹ÖªÊ¶£¬Ä㾡¿ÉÒÔÂýÂý¶Á¡£ÓÐЩ¸ÅÄî±È½ÏÄѶ®£¬Äã¿ÉÒÔÌø¹ý£¬²»Ó°ÏìÀí½âÕûÌåÄÚÈÝ¡£

ÕâÆªÎÄÕ´óÔ¼·ÖΪ3¸ö²¿·Ö£º

µ×²ãºÍÉϲãÊý¾Ý¿â×é¼þ¸Å¿ö

²éѯÓÅ»¯¹ý³Ì¸Å¿ö

ÊÂÎñºÍ»º³å³Ø¹ÜÀí¸Å¿ö

»Øµ½»ù´¡

ºÜ¾ÃºÜ¾ÃÒÔǰ£¨ÔÚÒ»¸öÒ£Ô¶¶øÓÖÒ£Ô¶µÄÐÇϵ¡­¡­)£¬¿ª·¢Õß±ØÐëÈ·ÇеØÖªµÀËûÃǵĴúÂëÐèÒª¶àÉÙ´ÎÔËËã¡£ËûÃǰÑËã·¨ºÍÊý¾Ý½á¹¹ÀμÇÓÚÐÄ£¬ÒòΪËûÃǵļÆËã»úÔËÐлºÂý£¬ÎÞ·¨³ÐÊܶÔCPUºÍÄÚ´æµÄÀË·Ñ¡£

ÔÚÕâÒ»²¿·Ö£¬ÎÒ½«ÌáÐÑ´ó¼ÒһЩÕâÀàµÄ¸ÅÄÒòΪËüÃǶÔÀí½âÊý¾Ý¿âÖÁ¹ØÖØÒª¡£ÎÒ»¹»á½éÉÜÊý¾Ý¿âË÷ÒýµÄ¸ÅÄî¡£

O(1) vs O(n^2)

ÏÖ½ñºÜ¶à¿ª·¢Õß²»¹ØÐÄʱ¼ä¸´ÔÓ¶È¡­¡­ËûÃÇÊǶԵġ£

µ«Êǵ±ÄãÓ¦¶Ô´óÁ¿µÄÊý¾Ý£¨ÎÒ˵µÄ¿É²»Ö»ÊdzÉǧÉÏÍò¹þ£©»òÕßÄãÒªÕùÈ¡ºÁÃë¼¶²Ù×÷£¬ÄÇôÀí½âÕâ¸ö¸ÅÄî¾ÍºÜ¹Ø¼üÁË¡£¶øÇÒÄã²ÂÔõô×Å£¬Êý¾Ý¿âҪͬʱ´¦ÀíÕâÁ½ÖÖÇé¾°£¡ÎÒ²»»áÕ¼ÓÃÄãÌ«³¤Ê±¼ä£¬Ö»ÒªÄãÄÜÃ÷°×ÕâÒ»µã¾Í¹»ÁË¡£Õâ¸ö¸ÅÄîÔÚÏÂÎÄ»á°ïÖúÎÒÃÇÀí½âʲôÊÇ»ùÓڳɱ¾µÄÓÅ»¯¡£

¸ÅÄî

ʱ¼ä¸´ÔÓ¶ÈÓÃÀ´¼ìÑéij¸öËã·¨´¦ÀíÒ»¶¨Á¿µÄÊý¾ÝÒª»¨¶à³¤Ê±¼ä¡£ÎªÁËÃèÊöÕâ¸ö¸´ÔÓ¶È£¬¼ÆËã»ú¿ÆÑ§¼ÒʹÓÃÊýѧÉϵġº¼òÃ÷½âÊÍËã·¨ÖеĴóO·ûºÅ¡»¡£Õâ¸ö±íʾ·¨ÓÃÒ»¸öº¯ÊýÀ´ÃèÊöËã·¨´¦Àí¸ø¶¨µÄÊý¾ÝÐèÒª¶àÉÙ´ÎÔËËã¡£

±ÈÈ磬µ±ÎÒ˵¡ºÕâ¸öËã·¨ÊÇÊÊÓà O(ijº¯Êý())¡»£¬ÎÒµÄÒâ˼ÊǶÔÓÚijЩÊý¾Ý£¬Õâ¸öËã·¨ÐèÒª ijº¯Êý(Êý¾ÝÁ¿) ´ÎÔËËãÀ´Íê³É¡£

ÖØÒªµÄ²»ÊÇÊý¾ÝÁ¿£¬¶øÊǵ±Êý¾ÝÁ¿Ôö¼ÓʱÔËËãÈçºÎÔö¼Ó¡£Ê±¼ä¸´ÔӶȲ»»á¸ø³öÈ·ÇеÄÔËËã´ÎÊý£¬µ«ÊǸø³öµÄÊÇÒ»ÖÖÀíÄî¡£

ͼÖпÉÒÔ¿´µ½²»Í¬ÀàÐ͵ĸ´ÔӶȵÄÑݱä¹ý³Ì£¬ÎÒÓÃÁ˶ÔÊý³ßÀ´½¨Õâ¸öͼ¡£¾ßÌåµã¶ù˵£¬Êý¾ÝÁ¿ÒԺܿìµÄËÙ¶È´Ó1ÌõÔö³¤µ½10ÒÚÌõ¡£ÎÒÃǿɵõ½ÈçϽáÂÛ£º

ÂÌ£ºO(1)»òÕ߽г£Êý½×¸´ÔÓ¶È£¬±£³ÖΪ³£Êý£¨Òª²»È˼ҾͲ»»á½Ð³£Êý½×¸´ÔÓ¶ÈÁË£©¡£

ºì£ºO(log(n))¶ÔÊý½×¸´ÔÓ¶È£¬¼´Ê¹ÔÚÊ®ÒÚ¼¶Êý¾ÝÁ¿Ê±Ò²ºÜµÍ¡£

·Û£º×îÔã¸âµÄ¸´ÔÓ¶ÈÊÇ O(n^2)£¬Æ½·½½×¸´ÔÓ¶È£¬ÔËËãÊý¿ìËÙÅòÕÍ¡£

ºÚºÍÀ¶£ºÁíÍâÁ½ÖÖ¸´ÔÓ¶È£¨µÄÔËËãÊýÒ²ÊÇ£©¿ìËÙÔö³¤¡£

Àý×Ó

Êý¾ÝÁ¿µÍʱ£¬O(1) ºÍ O(n^2)µÄÇø±ð¿ÉÒÔºöÂÔ²»¼Æ¡£±ÈÈ磬ÄãÓиöËã·¨Òª´¦Àí2000ÌõÔªËØ¡£

O(1) Ëã·¨»áÏûºÄ 1 ´ÎÔËËã

O(log(n)) Ëã·¨»áÏûºÄ 7 ´ÎÔËËã

O(n) Ëã·¨»áÏûºÄ 2000 ´ÎÔËËã

O(n*log(n)) Ëã·¨»áÏûºÄ 14,000 ´ÎÔËËã

O(n^2) Ëã·¨»áÏûºÄ 4,000,000 ´ÎÔËËã

O(1) ºÍ O(n^2) µÄÇø±ðËÆºõºÜ´ó£¨4°ÙÍò£©,µ«Äã×î¶àËðʧ 2 ºÁÃ룬ֻÊÇÒ»Õ£Ñ۵Ŧ·ò¡£È·Êµ£¬µ±½ñ´¦ÀíÆ÷ÿÃë¿É´¦ÀíÉÏÒڴεÄÔËËã¡£Õâ¾ÍÊÇΪʲôÐÔÄܺÍÓÅ»¯ÔںܶàITÏîÄ¿Öв»ÊÇÎÊÌâ¡£

ÎÒ˵¹ý£¬ÃæÁÙº£Á¿Êý¾ÝµÄʱºò£¬Á˽âÕâ¸ö¸ÅÄîÒÀÈ»ºÜÖØÒª¡£Èç¹ûÕâÒ»´ÎËã·¨ÐèÒª´¦Àí 1,000,000 ÌõÔªËØ£¨Õâ¶ÔÊý¾Ý¿âÀ´ËµÒ²²»Ëã´ó£©¡£

O(1) Ëã·¨»áÏûºÄ 1 ´ÎÔËËã

O(log(n)) Ëã·¨»áÏûºÄ 14 ´ÎÔËËã

O(n) Ëã·¨»áÏûºÄ 1,000,000 ´ÎÔËËã

O(n*log(n)) Ëã·¨»áÏûºÄ 14,000,000 ´ÎÔËËã

O(n^2) Ëã·¨»áÏûºÄ 1,000,000,000,000 ´ÎÔËËã

ÎÒûÓоßÌåËã¹ý£¬µ«ÎÒҪ˵£¬ÓÃO(n^2) Ëã·¨µÄ»°ÄãÓÐʱ¼äºÈ±­¿§·È£¨ÉõÖÁÔÙÐøÒ»±­£¡£©¡£Èç¹ûÔÚÊý¾ÝÁ¿ºóÃæ¼Ó¸ö0£¬ÄÇÄã¾Í¿ÉÒÔȥ˯´ó¾õÁË¡£

¼ÌÐøÉîÈë

ΪÁËÈÃÄãÄÜÃ÷°×

ËÑË÷Ò»¸öºÃµÄ¹þÏ£±í»áµÃµ½ O(1) ¸´ÔÓ¶È

ËÑË÷Ò»¸ö¾ùºâµÄÊ÷»áµÃµ½ O(log(n)) ¸´ÔÓ¶È

ËÑË÷Ò»¸öÕóÁлáµÃµ½ O(n) ¸´ÔÓ¶È

×îºÃµÄÅÅÐòËã·¨¾ßÓÐ O(n*log(n)) ¸´ÔÓ¶È

Ôã¸âµÄÅÅÐòËã·¨¾ßÓÐ O(n^2) ¸´ÔÓ¶È

×¢£ºÔÚ½ÓÏÂÀ´µÄ²¿·Ö£¬ÎÒÃǽ«»áÑо¿ÕâЩËã·¨ºÍÊý¾Ý½á¹¹¡£

ÓжàÖÖÀàÐ͵Äʱ¼ä¸´ÔÓ¶È

Ò»°ãÇé¿ö³¡¾°

×î¼ÑÇé¿ö³¡¾°

×î²îÇé¿ö³¡¾°

ʱ¼ä¸´ÔӶȾ­³£´¦ÓÚ×î²îÇé¿ö³¡¾°¡£

ÕâÀïÎÒֻ̽ÌÖʱ¼ä¸´ÔÓ¶È£¬µ«¸´ÔÓ¶È»¹°üÀ¨£º

Ëã·¨µÄÄÚ´æÏûºÄ

Ëã·¨µÄ´ÅÅÌ I/O ÏûºÄ

µ±È»»¹ÓÐ±È n^2 ¸üÔã¸âµÄ¸´ÔÓ¶È£¬±ÈÈ磺

n^4£º²î¾¢£¡ÎÒ½«ÒªÌáµ½µÄһЩËã·¨¾ß±¸ÕâÖÖ¸´ÔÓ¶È¡£

3^n£º¸ü²î¾¢£¡±¾ÎÄÖм䲿·ÖÑо¿µÄһЩËã·¨ÖÐÓÐÒ»¸ö¾ß±¸ÕâÖÖ¸´ÔÓ¶È£¨¶øÇÒÔںܶàÊý¾Ý¿âÖл¹ÕæµÄʹÓÃÁË£©¡£

½×³Ë n£ºÄãÓÀÔ¶µÃ²»µ½½á¹û£¬¼´±ãÔÚÉÙÁ¿Êý¾ÝµÄÇé¿öÏ¡£

n^n£ºÈç¹ûÄã·¢Õ¹µ½ÕâÖÖ¸´ÔÓ¶ÈÁË£¬ÄÇÄãÓ¦¸ÃÎÊÎÊ×Ô¼ºITÊDz»ÊÇÄãµÄ²Ë¡£

×¢£ºÎÒ²¢Ã»Óиø³ö¡º´óO±íʾ·¨¡»µÄÕæÕý¶¨Ò壬ֻÊÇÀûÓÃÕâ¸ö¸ÅÄî¡£¿ÉÒÔ¿´¿´Î¬»ù°Ù¿ÆÉϵÄÕâÆªÎÄÕ¡£

ºÏ²¢ÅÅÐò

µ±ÄãÒª¶ÔÒ»¸ö¼¯ºÏÅÅÐòʱÄãÔõô×ö£¿Ê²Ã´£¿µ÷Óà sort() º¯Êý¡­¡­ºÃ°É£¬ËãÄã¶ÔÁË¡­¡­µ«ÊǶÔÓÚÊý¾Ý¿â£¬ÄãÐèÒªÀí½âÕâ¸ö sort() º¯ÊýµÄ¹¤×÷Ô­Àí¡£

ÓÅÐãµÄÅÅÐòËã·¨Óкü¸¸ö£¬ÎÒ²àÖØÓÚ×îÖØÒªµÄÒ»ÖÖ£ººÏ²¢ÅÅÐò¡£ÄãÏÖÔÚ¿ÉÄÜ»¹²»Á˽âÊý¾ÝÅÅÐòÓÐʲôÓ㬵«¿´Íê²éѯÓÅ»¯²¿·ÖºóÄã¾Í»áÖªµÀÁË¡£ÔÙÕߣ¬ºÏ²¢ÅÅÐòÓÐÖúÓÚÎÒÃÇÒÔºóÀí½âÊý¾Ý¿â³£¼ûµÄÁª½Ó²Ù×÷£¬¼´ºÏ²¢Áª½Ó ¡£

ºÏ²¢

ÓëºÜ¶àÓÐÓõÄËã·¨ÀàËÆ£¬ºÏ²¢ÅÅÐò»ùÓÚÕâÑùÒ»¸ö¼¼ÇÉ£º½« 2 ¸ö´óСΪ N/2 µÄÒÑÅÅÐòÐòÁкϲ¢ÎªÒ»¸ö N ÔªËØÒÑÅÅÐòÐòÁнöÐèÒª N ´Î²Ù×÷¡£Õâ¸ö·½·¨½Ð×öºÏ²¢¡£

ÎÒÃÇÓøö¼òµ¥µÄÀý×ÓÀ´¿´¿´ÕâÊÇʲôÒâ˼£º

ͨ¹ý´ËͼÄã¿ÉÒÔ¿´µ½£¬ÔÚ 2 ¸ö 4ÔªËØÐòÁÐÀïÄãÖ»ÐèÒªµü´úÒ»´Î£¬¾ÍÄܹ¹½¨×îÖÕµÄ8ÔªËØÒÑÅÅÐòÐòÁУ¬ÒòΪÁ½¸ö4ÔªËØÐòÁÐÒѾ­ÅźÃÐòÁË£º

1) ÔÚÁ½¸öÐòÁÐÖУ¬±È½Ïµ±Ç°ÔªËØ£¨µ±Ç°=Í·Ò»´Î³öÏֵĵÚÒ»¸ö£©

2) È»ºóÈ¡³ö×îСµÄÔªËØ·Å½ø8ÔªËØÐòÁÐÖÐ

3) ÕÒµ½£¨Á½¸ö£©ÐòÁеÄÏÂÒ»¸öÔªËØ£¬(±È½Ïºó)È¡³ö×îСµÄ

ÖØ¸´1¡¢2¡¢3²½Ö裬ֱµ½ÆäÖÐÒ»¸öÐòÁÐÖеÄ×îºóÒ»¸öÔªËØ

È»ºóÈ¡³öÁíÒ»¸öÐòÁÐÊ£ÓàµÄÔªËØ·ÅÈë8ÔªËØÐòÁÐÖС£

Õâ¸ö·½·¨Ö®ËùÒÔÓÐЧ£¬ÊÇÒòΪÁ½¸ö4ÔªËØÐòÁж¼ÒѾ­ÅźÃÐò£¬Äã²»ÐèÒªÔÙ¡º»Øµ½¡»ÐòÁÐÖвéÕұȽϡ£

¼ÈÈ»ÎÒÃÇÃ÷°×ÁËÕâ¸ö¼¼ÇÉ£¬ÏÂÃæ¾ÍÊÇÎҵĺϲ¢ÅÅÐòα´úÂë¡£

array mergeSort(array a)
if(length(a)==1)
return a[0];
end if

//recursive calls
[left_array right_array] := split_into_2_equally_sized_arrays(a);
array new_left_array := mergeSort(left_array);
array new_right_array := mergeSort(right_array);

//merging the 2 small ordered arrays into a big one
array result := merge(new_left_array,new_right_array);
return result;

ºÏ²¢ÅÅÐòÊǰÑÎÊÌâ²ð·ÖΪСÎÊÌ⣬ͨ¹ý½â¾öСÎÊÌâÀ´½â¾ö×î³õµÄÎÊÌ⣨ע£ºÕâÖÖËã·¨½Ð·ÖÖ稣¬¼´¡º·Ö¶øÖÎÖ®¡¢¸÷¸ö»÷ÆÆ¡»£©¡£Èç¹ûÄã²»¶®£¬²»Óõ£ÐÄ£¬ÎÒµÚÒ»´Î½Ó´¥Ê±Ò²²»¶®¡£Èç¹ûÄܰïÖúÄãÀí½âµÄ»°£¬ÎÒÈÏΪÕâ¸öËã·¨ÊǸöÁ½²½Ëã·¨£º

²ð·Ö½×¶Î£¬½«ÐòÁзÖΪ¸üСµÄÐòÁÐ

ÅÅÐò½×¶Î£¬°ÑСµÄÐòÁкÏÔÚÒ»Æð£¨Ê¹Óúϲ¢Ëã·¨£©À´¹¹³É¸ü´óµÄÐòÁÐ

²ð·Ö½×¶Î

ÔÚ²ð·Ö½×¶Î¹ý³ÌÖУ¬Ê¹ÓÃ3¸ö²½Ö轫ÐòÁзÖΪһԪÐòÁС£²½ÖèÊýÁ¿µÄÖµÊÇ log(N) £¨ÒòΪ N=8, log(N)=3£©¡£¡¾ÒëÕß×¢£ºµ×ÊýΪ2£¬ÏÂÎÄÓÐ˵Ã÷¡¿

ÎÒÔõô֪µÀÕâ¸öµÄ£¿

ÎÒÊÇÌì²Å£¡Ò»¾ä»°£ºÊýѧ¡£µÀÀíÊÇÿһ²½¶¼°ÑÔ­ÐòÁеij¤¶È³ýÒÔ2£¬²½ÖèÊý¾ÍÊÇÄãÄܰÑÔ­ÐòÁг¤¶È³ýÒÔ2µÄ´ÎÊý¡£ÕâÕýºÃÊǶÔÊýµÄ¶¨Ò壨ÔÚµ×ÊýΪ2ʱ£©¡£

ÅÅÐò½×¶Î

ÔÚÅÅÐò½×¶Î£¬Äã´ÓÒ»ÔªÐòÁпªÊ¼¡£ÔÚÿһ¸ö²½ÖèÖУ¬ÄãÓ¦Óöà´ÎºÏ²¢²Ù×÷£¬³É±¾Ò»¹²ÊÇ N=8 ´ÎÔËËã¡£

µÚÒ»²½£¬4 ´ÎºÏ²¢£¬Ã¿´Î³É±¾ÊÇ 2 ´ÎÔËËã¡£

µÚ¶þ²½£¬2 ´ÎºÏ²¢£¬Ã¿´Î³É±¾ÊÇ 4 ´ÎÔËËã¡£

µÚÈý²½£¬1 ´ÎºÏ²¢£¬³É±¾ÊÇ 8 ´ÎÔËËã¡£

ÒòΪÓÐ log(N) ¸ö²½Ö裬ÕûÌå³É±¾ÊÇ N*log(N) ´ÎÔËËã¡£

¡¾ÒëÕß×¢£ºÕâ¸öÍêÕûµÄ¶¯Í¼ÑÝʾÁ˲ð·ÖºÍÅÅÐòµÄÈ«¹ý³Ì£¬²»¶¯´Á´ó¡£¡¿

ºÏ²¢ÅÅÐòµÄÇ¿´óÖ®´¦

ΪʲôÕâ¸öËã·¨Èç´ËÇ¿´ó£¿

ÒòΪ£º

Äã¿ÉÒÔ¸ü¸ÄËã·¨£¬ÒÔ±ãÓÚ½ÚÊ¡ÄÚ´æ¿Õ¼ä£¬·½·¨ÊDz»´´½¨ÐµÄÐòÁжøÊÇÖ±½ÓÐÞ¸ÄÊäÈëÐòÁС£

×¢£ºÕâÖÖËã·¨½Ð¡ºÔ­µØËã·¨¡»(in-place algorithm)

Äã¿ÉÒÔ¸ü¸ÄËã·¨£¬ÒÔ±ãÓÚͬʱʹÓôÅÅ̿ռäºÍÉÙÁ¿ÄÚ´æ¶ø±ÜÃâ¾ÞÁ¿´ÅÅÌ I/O¡£·½·¨ÊÇÖ»ÏòÄÚ´æÖмÓÔØµ±Ç°´¦ÀíµÄ²¿·Ö¡£ÔÚ½ö½ö100MBµÄÄڴ滺³åÇøÄÚÅÅÐòÒ»¸ö¼¸¸öGBµÄ±íʱ£¬ÕâÊǸöºÜÖØÒªµÄ¼¼ÇÉ¡£

×¢£ºÕâÖÖËã·¨½Ð¡ºÍⲿÅÅÐò¡»(external sorting)¡£

Äã¿ÉÒÔ¸ü¸ÄËã·¨£¬ÒÔ±ãÓÚÔÚ ¶à´¦ÀíÆ÷/¶àÏß³Ì/¶à·þÎñÆ÷ ÉÏÔËÐС£

±ÈÈ磬·Ö²¼Ê½ºÏ²¢ÅÅÐòÊÇHadoop£¨ÄǸöÖøÃûµÄ´óÊý¾Ý¿ò¼Ü£©µÄ¹Ø¼ü×é¼þÖ®Ò»¡£

Õâ¸öËã·¨¿ÉÒÔµãʯ³É½ð£¨ÊÂʵÈç´Ë£¡£©

Õâ¸öÅÅÐòËã·¨ÔÚ´ó¶àÊý£¨Èç¹û²»ÊÇÈ«²¿µÄ»°£©Êý¾Ý¿âÖÐʹÓ㬵«ÊÇËü²¢²»ÊÇΨһËã·¨¡£Èç¹ûÄãÏë¶àÁ˽âһЩ£¬Äã¿ÉÒÔ¿´¿´ ÕâÆªÂÛÎÄ£¬Ì½ÌÖµÄÊÇÊý¾Ý¿âÖг£ÓÃÅÅÐòËã·¨µÄÓÅÊÆºÍÁÓÊÆ¡£

ÕóÁУ¬Ê÷ºÍ¹þÏ£±í

¼ÈÈ»ÎÒÃÇÒѾ­Á˽âÁËʱ¼ä¸´ÔӶȺÍÅÅÐò±³ºóµÄÀíÄÎÒ±ØÐëÒªÏòÄã½éÉÜ3ÖÖÊý¾Ý½á¹¹ÁË¡£Õâ¸öºÜÖØÒª£¬ÒòΪËüÃÇÊÇÏÖ´úÊý¾Ý¿âµÄÖ§Öù¡£ÎÒ»¹»á½éÉÜÊý¾Ý¿âË÷ÒýµÄ¸ÅÄî¡£

ÕóÁÐ

¶þάÕóÁÐÊÇ×î¼òµ¥µÄÊý¾Ý½á¹¹¡£Ò»¸ö±í¿ÉÒÔ¿´×÷ÊǸöÕóÁУ¬±ÈÈ磺

Õâ¸ö¶þάÕóÁÐÊÇ´øÓÐÐÐÓëÁÐµÄ±í£º

ÿ¸öÐдú±íÒ»¸öÖ÷Ìå

ÁÐÓÃÀ´ÃèÊöÖ÷ÌåµÄÌØÕ÷

ÿ¸öÁб£´æÄ³Ò»ÖÖÀàÐͶÔÊý¾Ý£¨ÕûÊý¡¢×Ö·û´®¡¢ÈÕÆÚ¡­¡­£©

ËäÈ»ÓÃÕâ¸ö·½·¨±£´æºÍÊÓ¾õ»¯Êý¾ÝºÜ°ô£¬µ«Êǵ±ÄãÒª²éÕÒÌØ¶¨µÄÖµËü¾ÍºÜÔã¸âÁË¡£ ¾Ù¸öÀý×Ó£¬Èç¹ûÄãÒªÕÒµ½ËùÓÐÔÚ UK ¹¤×÷µÄÈË£¬Äã±ØÐë²é¿´Ã¿Ò»ÐÐÒÔÅжϸÃÐÐÊÇ·ñÊôÓÚ UK ¡£Õâ»áÔì³É N ´ÎÔËËãµÄ³É±¾£¨N µÈÓÚÐÐÊý£©£¬»¹²»ÀµÂµ«ÊÇÓÐûÓиü¿ìµÄ·½·¨ÄØ£¿ÕâʱºòÊ÷¾Í¿ÉÒԵdz¡ÁË£¨»ò¿ªÊ¼Æð×÷ÓÃÁË£©¡£

Ê÷ºÍÊý¾Ý¿âË÷Òý

¶þ²æ²éÕÒÊ÷ÊÇ´øÓÐÌØÊâÊôÐԵĶþ²æÊ÷£¬Ã¿¸ö½ÚµãµÄ¹Ø¼ü×Ö±ØÐ룺

±È±£´æÔÚ×ó×ÓÊ÷µÄÈκμüÖµ¶¼Òª´ó

±È±£´æÔÚÓÒ×ÓÊ÷µÄÈκμüÖµ¶¼ÒªÐ¡

¡¾ÒëÕß×¢£ºbinary search tree£¬¶þ²æ²éÕÒÊ÷/¶þ²æËÑË÷Ê÷£¬»ò³Æ Binary Sort Tree ¶þ²æÅÅÐòÊ÷¡£¼û°Ù¶È°Ù¿Æ ¡¿

¸ÅÄî

Ê÷ÓÐ N=15 ¸öÔªËØ¡£±È·½ËµÎÒÒªÕÒ208£º

ÎÒ´Ó¼üֵΪ 136 µÄ¸ù¿ªÊ¼£¬ÒòΪ 136<208£¬ÎÒÈ¥ÕÒ½Úµã136µÄÓÒ×ÓÊ÷¡£

398>208£¬ËùÒÔÎÒÈ¥ÕÒ½Úµã398µÄ×ó×ÓÊ÷

250>208£¬ËùÒÔÎÒÈ¥ÕÒ½Úµã250µÄ×ó×ÓÊ÷

200<208£¬ËùÒÔÎÒÈ¥ÕÒ½Úµã200µÄÓÒ×ÓÊ÷¡£µ«ÊÇ 200 ûÓÐÓÒ×ÓÊ÷£¬Öµ²»´æÔÚ£¨ÒòΪÈç¹û´æÔÚ£¬Ëü»áÔÚ 200 µÄÓÒ×ÓÊ÷£©

ÏÖÔڱȷ½ËµÎÒÒªÕÒ40

ÎÒ´Ó¼üֵΪ136µÄ¸ù¿ªÊ¼£¬ÒòΪ 136>40£¬ËùÒÔÎÒÈ¥ÕÒ½Úµã136µÄ×ó×ÓÊ÷¡£

80>40£¬ËùÒÔÎÒÈ¥ÕÒ½Úµã 80 µÄ×ó×ÓÊ÷

40=40£¬½Úµã´æÔÚ¡£ÎÒ³éÈ¡³ö½ÚµãÄÚ²¿ÐеÄID£¨Í¼ÖÐûÓл­£©ÔÙÈ¥±íÖвéÕÒ¶ÔÓ¦µÄ ROW ID¡£

ÖªµÀ ROW IDÎÒ¾ÍÖªµÀÁËÊý¾ÝÔÚ±íÖжԾ«È·Î»Ö㬾ͿÉÒÔÁ¢¼´»ñÈ¡Êý¾Ý¡£

×îºó£¬Á½´Î²éѯµÄ³É±¾¾ÍÊÇÊ÷ÄÚ²¿µÄ²ãÊý¡£Èç¹ûÄã×ÐϸÔĶÁÁ˺ϲ¢ÅÅÐòµÄ²¿·Ö£¬Äã¾ÍÓ¦¸ÃÃ÷°×Ò»¹²ÓÐ log(N)²ã¡£ËùÒÔÕâ¸ö²éѯµÄ³É±¾ÊÇ log(N)£¬²»´í°¡£¡

»Øµ½ÎÒÃǵÄÎÊÌâ

ÉÏÎÄ˵µÄºÜ³éÏó£¬ÎÒÃÇ»ØÀ´¿´¿´ÎÒÃǵÄÎÊÌâ¡£Õâ´Î²»ÓÃɵɵµÄÊý×ÖÁË£¬ÏëÏóÒ»ÏÂǰ±íÖдú±íijÈ˵Ĺú¼ÒµÄ×Ö·û´®¡£¼ÙÉèÄãÓиöÊ÷°üº¬±íÖеÄÁСºcountry¡»£º

Èç¹ûÄãÏëÖªµÀË­ÔÚ UK ¹¤×÷

ÄãÔÚÊ÷ÖвéÕÒ´ú±í UK µÄ½Úµã

ÔÚ¡ºUK ½Úµã¡»Äã»áÕÒµ½ UK Ô±¹¤ÄÇЩÐеÄλÖÃ

Õâ´ÎËÑË÷Ö»Ðè log(N) ´ÎÔËË㣬¶øÈç¹ûÄãÖ±½ÓʹÓÃÕóÁÐÔòÐèÒª N ´ÎÔËËã¡£Äã¸Õ¸ÕÏëÏóµÄ¾ÍÊÇÒ»¸öÊý¾Ý¿âË÷Òý¡£

B+Ê÷Ë÷Òý

²éÕÒÒ»¸öÌØ¶¨ÖµÕâ¸öÊ÷ͦºÃÓ㬵«Êǵ±ÄãÐèÒª²éÕÒÁ½¸öÖµÖ®¼äµÄ¶à¸öÔªËØÊ±£¬¾Í»áÓдóÂé·³ÁË¡£ÄãµÄ³É±¾½«ÊÇ O(N)£¬ÒòΪÄã±ØÐë²éÕÒÊ÷µÄÿһ¸ö½Úµã£¬ÒÔÅжÏËüÊÇ·ñ´¦ÓÚÄÇ 2 ¸öÖµÖ®¼ä£¨ÀýÈ磬¶ÔÊ÷ʹÓÃÖÐÐò±éÀú£©¡£¶øÇÒÕâ¸ö²Ù×÷²»ÊÇ´ÅÅÌI/OÓÐÀûµÄ£¬ÒòΪÄã±ØÐë¶ÁÈ¡Õû¸öÊ÷¡£ÎÒÃÇÐèÒªÕÒµ½¸ßЧµÄ·¶Î§²éѯ·½·¨¡£ÎªÁ˽â¾öÕâ¸öÎÊÌ⣬ÏÖ´úÊý¾Ý¿âʹÓÃÁËÒ»ÖÖÐÞ¶©°æµÄÊ÷£¬½Ð×öB+Ê÷¡£ÔÚÒ»¸öB+Ê÷À

Ö»ÓÐ×îµ×²ãµÄ½Úµã£¨Ò¶×ӽڵ㣩²Å±£´æÐÅÏ¢£¨Ïà¹Ø±íµÄÐÐλÖã©

ÆäËü½ÚµãÖ»ÊÇÔÚËÑË÷ÖÐÓÃÀ´Ö¸Òýµ½ÕýÈ·½ÚµãµÄ¡£

½Úµã¸ü¶àÁË£¨¶àÁËÁ½±¶£©¡£È·Êµ£¬ÄãÓÐÁ˶îÍâµÄ½Úµã£¬ËüÃǾÍÊǰïÖúÄãÕÒµ½ÕýÈ·½ÚµãµÄ¡º¾ö²ß½Úµã¡»£¨ÕýÈ·½Úµã±£´æ×ÅÏà¹Ø±íÖÐÐеÄλÖã©¡£µ«ÊÇËÑË÷¸´ÔÓ¶È»¹ÊÇÔÚ O(log(N))£¨Ö»¶àÁËÒ»²ã£©¡£Ò»¸öÖØÒªµÄ²»Í¬µãÊÇ£¬×îµ×²ãµÄ½ÚµãÊǸúºóÐø½ÚµãÏàÁ¬½ÓµÄ¡£

ÓÃÕâ¸ö B+Ê÷£¬¼ÙÉèÄãÒªÕÒ40µ½100¼äµÄÖµ£º

ÄãÖ»ÐèÒªÕÒ 40£¨Èô40²»´æÔÚÔòÕÒ40Ö®ºó×îÌù½üµÄÖµ£©£¬¾ÍÏñÄãÔÚÉÏÒ»¸öÊ÷ÖÐËù×öµÄÄÇÑù¡£

È»ºóÓÃÄÇЩÁ¬½ÓÀ´ÊÕ¼¯40µÄºóÐø½Úµã£¬Ö±µ½ÕÒµ½100¡£

±È·½ËµÄãÕÒµ½ÁË M ¸öºóÐø½Úµã£¬Ê÷×ܹ²ÓÐ N ¸ö½Úµã¡£¶ÔÖ¸¶¨½ÚµãµÄËÑË÷³É±¾ÊÇ log(N)£¬¸úÉÏÒ»¸öÊ÷Ïàͬ¡£µ«Êǵ±ÄãÕÒµ½Õâ¸ö½Úµã£¬ÄãµÃͨ¹ýºóÐø½ÚµãµÄÁ¬½ÓµÃµ½ M ¸öºóÐø½Úµã£¬ÕâÐèÒª M ´ÎÔËËã¡£ÄÇôÕâ´ÎËÑË÷Ö»ÏûºÄÁË M+log(N) ´ÎÔËËã£¬Çø±ðÓÚÉÏÒ»¸öÊ÷ËùÓÃµÄ N ´ÎÔËËã¡£´ËÍ⣬Äã²»ÐèÒª¶ÁÈ¡Õû¸öÊ÷£¨½öÐèÒª¶Á M+log(N) ¸ö½Úµã£©,ÕâÒâζןüÉٵĴÅÅÌ·ÃÎÊ¡£Èç¹û M ºÜС£¨±ÈÈç 200 ÐУ©²¢ÇÒ N ºÜ´ó£¨1,000,000£©£¬Äǽá¹û¾ÍÊÇÌìÈÀÖ®±ðÁË¡£

È»¶ø»¹ÓÐеÄÎÊÌ⣨ÓÖÀ´ÁË£¡£©¡£Èç¹ûÄãÔÚÊý¾Ý¿âÖÐÔö¼Ó»òɾ³ýÒ»ÐУ¨´Ó¶øÔÚÏà¹ØµÄ B+Ê÷Ë÷ÒýÀ£º

Äã±ØÐëÔÚB+Ê÷ÖеĽڵãÖ®¼ä±£³Ö˳Ðò£¬·ñÔò½Úµã»á±äµÃÒ»ÍÅÔ㣬ÄãÎÞ·¨´ÓÖÐÕÒµ½ÏëÒªµÄ½Úµã¡£

Äã±ØÐ뾡¿ÉÄܽµµÍB+Ê÷µÄ²ãÊý£¬·ñÔò O(log(N)) ¸´ÔÓ¶È»á±ä³É O(N)¡£

»»¾ä»°Ëµ£¬B+Ê÷ÐèÒª×ÔÎÒÕûÀíºÍ×ÔÎÒÆ½ºâ¡£Ð»ÌìлµØ£¬ÎÒÃÇÓÐÖÇÄÜɾ³ýºÍ²åÈë¡£µ«ÊÇÕâÑùÒ²´øÀ´Á˳ɱ¾£ºÔÚB+Ê÷ÖУ¬²åÈëºÍɾ³ý²Ù×÷ÊÇ O(log(N)) ¸´ÔÓ¶È¡£ËùÒÔÓÐЩÈËÌýµ½¹ýʹÓÃÌ«¶àË÷Òý²»ÊǸöºÃÖ÷ÒâÕâÀà˵·¨¡£Ã»´í£¬Äã¼õÂýÁË¿ìËÙ²åÈë/¸üÐÂ/ɾ³ý±íÖеÄÒ»¸öÐеIJÙ×÷£¬ÒòΪÊý¾Ý¿âÐèÒªÒÔ´ú¼Û¸ß°ºµÄÿË÷Òý O(log(N)) ÔËËãÀ´¸üбíµÄË÷Òý¡£ÔÙÕߣ¬Ôö¼ÓË÷ÒýÒâζןøÊÂÎñ¹ÜÀíÆ÷´øÀ´¸ü¶àµÄ¹¤×÷¸ººÉ£¨ÔÚ±¾ÎĽáβÎÒÃÇ»á̽ÌÖÕâ¸ö¹ÜÀíÆ÷£©¡£

ÏëÁ˽â¸ü¶àϸ½Ú£¬Äã¿ÉÒÔ¿´¿´ Wikipedia ÉÏÕâÆª¹ØÓÚB+Ê÷µÄÎÄÕ¡£Èç¹ûÄãÏëÒªÊý¾Ý¿âÖÐʵÏÖB+Ê÷µÄÀý×Ó£¬¿´¿´MySQLºËÐÄ¿ª·¢ÈËԱдµÄÕâÆªÎÄÕ ºÍ ÕâÆªÎÄÕ¡£Á½ÆªÎÄÕ¶¼ÖÂÁ¦ÓÚ̽ÌÖ innoDB(MySQLÒýÇæ)ÈçºÎ´¦ÀíË÷Òý¡£

¹þÏ£±í

ÎÒÃÇ×îºóÒ»¸öÖØÒªµÄÊý¾Ý½á¹¹ÊǹþÏ£±í¡£µ±ÄãÏë¿ìËÙ²éÕÒֵʱ£¬¹þÏ£±íÊǷdz£ÓÐÓõġ£¶øÇÒ£¬Àí½â¹þÏ£±í»á°ïÖúÎÒÃǽÓÏÂÀ´Àí½âÒ»¸öÊý¾Ý¿â³£¼ûµÄÁª½Ó²Ù×÷£¬½Ð×ö¡º¹þÏ£Áª½Ó¡»¡£Õâ¸öÊý¾Ý½á¹¹Ò²±»Êý¾Ý¿âÓÃÀ´±£´æÒ»Ð©ÄÚ²¿µÄ¶«Î÷£¨±ÈÈçËø±í»òÕß»º³å³Ø£¬ÎÒÃÇÔÚÏÂÎÄ»áÑо¿ÕâÁ½¸ö¸ÅÄ¡£

¹þÏ£±íÕâÖÖÊý¾Ý½á¹¹¿ÉÒÔÓùؼü×ÖÀ´¿ìËÙÕÒµ½Ò»¸öÔªËØ¡£ÎªÁ˹¹½¨Ò»¸ö¹þÏ£±í£¬ÄãÐèÒª¶¨Ò壺

ÔªËØµÄ¹Ø¼ü×Ö

¹Ø¼ü×ֵĹþÏ£º¯Êý¡£¹Ø¼ü×Ö¼ÆËã³öÀ´µÄ¹þÏ£Öµ¸ø³öÁËÔªËØµÄλÖ㨽Ð×ö¹þϣͰ£©¡£

¹Ø¼ü×ֱȽϺ¯Êý¡£Ò»µ©ÄãÕÒµ½ÕýÈ·µÄ¹þϣͰ£¬Äã±ØÐëÓñȽϺ¯ÊýÔÚͰÄÚÕÒµ½ÄãÒªµÄÔªËØ¡£

Ò»¸ö¼òµ¥µÄÀý×Ó

ÎÒÃÇÀ´¿´Ò»¸öÐÎÏ󻯵ÄÀý×Ó£º

Õâ¸ö¹þÏ£±íÓÐ10¸ö¹þϣͰ¡£ÒòΪÎÒÀÁ£¬ÎÒÖ»¸ø³ö5¸öͰ£¬µ«ÊÇÎÒÖªµÀÄãºÜ´ÏÃ÷£¬ËùÒÔÎÒÈÃÄãÏëÏóÆäËüµÄ5¸öͰ¡£ÎÒÓõĹþÏ£º¯ÊýÊǹؼü×Ö¶Ô10ȡģ£¬Ò²¾ÍÊÇÎÒÖ»±£ÁôÔªËØ¹Ø¼ü×ÖµÄ×îºóһ룬ÓÃÀ´²éÕÒËüµÄ¹þϣͰ£º

Èç¹ûÔªËØ×îºóһλÊÇ 0£¬Ôò½øÈë¹þϣͰ0£¬

Èç¹ûÔªËØ×îºóһλÊÇ 1£¬Ôò½øÈë¹þϣͰ1£¬

Èç¹ûÔªËØ×îºóһλÊÇ 2£¬Ôò½øÈë¹þϣͰ2£¬

¡­ÎÒÓõıȽϺ¯ÊýÖ»ÊÇÅжÏÁ½¸öÕûÊýÊÇ·ñÏàµÈ¡£

±È·½ËµÄãÒªÕÒÔªËØ 78£º

¹þÏ£±í¼ÆËã 78 µÄ¹þÏ£Â룬µÈÓÚ 8¡£

²éÕÒ¹þϣͰ 8£¬ÕÒµ½µÄµÚÒ»¸öÔªËØÊÇ 78¡£

·µ»ØÔªËØ 78¡£

²éѯ½öºÄ·ÑÁË 2 ´ÎÔËË㣨1´Î¼ÆËã¹þÏ£Öµ£¬ÁíÒ»´ÎÔÚ¹þϣͰÖвéÕÒÔªËØ£©¡£

ÏÖÔÚ£¬±È·½ËµÄãÒªÕÒÔªËØ 59£º

¹þÏ£±í¼ÆËã 59 µÄ¹þÏ£Â룬µÈÓÚ9¡£

²éÕÒ¹þϣͰ 9£¬µÚÒ»¸öÕÒµ½µÄÔªËØÊÇ 99¡£ÒòΪ 99 ²»µÈÓÚ 59£¬ ÄÇô 99 ²»ÊÇÕýÈ·µÄÔªËØ¡£

ÓÃͬÑùµÄÂß¼­£¬²éÕÒµÚ¶þ¸öÔªËØ(9)£¬µÚÈý¸ö(79)£¬¡­¡­£¬×îºóÒ»¸ö(29)¡£

ÔªËØ²»´æÔÚ¡£

ËÑË÷ºÄ·ÑÁË 7 ´ÎÔËËã¡£

Ò»¸öºÃµÄ¹þÏ£º¯Êý

Äã¿ÉÒÔ¿´µ½£¬¸ù¾ÝÄã²éÕÒµÄÖµ£¬³É±¾²¢²»Ïàͬ¡£

Èç¹ûÎҰѹþÏ£º¯Êý¸ÄΪ¹Ø¼ü×Ö¶Ô 1,000,000 ȡ죍¾ÍÊÇ˵ȡºó6λÊý×Ö£©£¬µÚ¶þ´ÎËÑË÷Ö»ÏûºÄÒ»´ÎÔËË㣬ÒòΪ¹þϣͰ 00059 ÀïÃæÃ»ÓÐÔªËØ¡£ÕæÕýµÄÌôÕ½ÊÇÕÒµ½ºÃµÄ¹þÏ£º¯Êý£¬ÈùþϣͰÀï°üº¬·Ç³£ÉÙµÄÔªËØ¡£

ÔÚÎÒµÄÀý×ÓÀÕÒµ½Ò»¸öºÃµÄ¹þÏ£º¯ÊýºÜÈÝÒ×£¬µ«ÕâÊǸö¼òµ¥µÄÀý×Ó¡£µ±¹Ø¼ü×ÖÊÇÏÂÁÐÐÎʽʱ£¬ºÃµÄ¹þÏ£º¯Êý¾Í¸üÄÑÕÒÁË£º

1 ¸ö×Ö·û´®£¨±ÈÈçÒ»¸öÈ˵ÄÐÕ£©

2 ¸ö×Ö·û´®£¨±ÈÈçÒ»¸öÈ˵ÄÐÕºÍÃû£©

2 ¸ö×Ö·û´®ºÍÒ»¸öÈÕÆÚ£¨±ÈÈçÒ»¸öÈ˵ÄÐÕ¡¢ÃûºÍ³öÉúÄêÔÂÈÕ£©

¡­

Èç¹ûÓÐÁ˺õĹþÏ£º¯Êý£¬ÔÚ¹þÏ£±íÀïËÑË÷µÄʱ¼ä¸´ÔÓ¶ÈÊÇ O(1)¡£

ÕóÁÐ vs ¹þÏ£±í

Ϊʲô²»ÓÃÕóÁÐÄØ£¿

àÅ£¬ÄãÎʵúá£

Ò»¸ö¹þÏ£±í¿ÉÒÔÖ»×°ÔØÒ»°ëµ½Äڴ棬ʣϵĹþϣͰ¿ÉÒÔÁôÔÚÓ²ÅÌÉÏ¡£

ÓÃÕóÁеϰ£¬ÄãÐèÒªÒ»¸öÁ¬ÐøÄÚ´æ¿Õ¼ä¡£Èç¹ûÄã¼ÓÔØÒ»¸ö´ó±í£¬ºÜÄÑ·ÖÅä×ã¹»µÄÁ¬ÐøÄÚ´æ¿Õ¼ä¡£

ÓùþÏ£±íµÄ»°£¬Äã¿ÉÒÔÑ¡ÔñÄãÒªµÄ¹Ø¼ü×Ö£¨±ÈÈ磬һ¸öÈ˵Ĺú¼ÒºÍÐÕÊÏ£©¡£

ÏëÒª¸üÏêϸµÄÐÅÏ¢£¬Äã¿ÉÒÔÔĶÁÎÒÔÚJava HashMap ÉϵÄÎÄÕ£¬ÊǹØÓÚ¸ßЧ¹þÏ£±íʵÏֵġ£Äã²»ÐèÒªÁ˽âJava¾ÍÄÜÀí½âÎÄÕÂÀïµÄ¸ÅÄî¡£

È«¾Ö¸ÅÀÀ

ÎÒÃÇÒѾ­Á˽âÁËÊý¾Ý¿âÄÚ²¿µÄ»ù±¾×é¼þ£¬ÏÖÔÚÎÒÃÇÐèÒª»ØÀ´¿´¿´Êý¾Ý¿âµÄȫòÁË¡£

Êý¾Ý¿âÊÇÒ»¸öÒ×ÓÚ·ÃÎʺÍÐ޸ĵÄÐÅÏ¢¼¯ºÏ¡£²»¹ý¼òµ¥µÄÒ»¶ÑÎļþÒ²ÄÜ´ïµ½Õâ¸öЧ¹û¡£ÊÂʵÉÏ£¬ÏñSQLiteÕâÑù×î¼òµ¥µÄÊý¾Ý¿âÒ²Ö»ÊÇÒ»¶ÑÎļþ¶øÒÑ£¬µ«SQLiteÊǾ«ÐÄÉè¼ÆµÄÒ»¶ÑÎļþ£¬ÒòΪËüÔÊÐíÄ㣺

ʹÓÃÊÂÎñÀ´È·±£Êý¾ÝµÄ°²È«ºÍÒ»ÖÂÐÔ

¿ìËÙ´¦Àí°ÙÍòÌõÒÔÉϵÄÊý¾Ý

Êý¾Ý¿âÒ»°ã¿ÉÒÔÓÃÈçÏÂͼÐÎÀ´Àí½â£º

׫дÕⲿ·Ö֮ǰ£¬ÎÒ¶Á¹ýºÜ¶àÊé/ÂÛÎÄ£¬ËüÃǶ¼ÒÔ×Ô¼ºµÄ·½Ê½ÃèÊöÊý¾Ý¿â¡£ËùÒÔ£¬ÎÒ²»»áÌØ±ð¹Ø×¢ÈçºÎ×éÖ¯Êý¾Ý¿â»òÕßÈçºÎÃüÃû¸÷ÖÖ½ø³Ì£¬ÒòΪÎÒÑ¡ÔñÁË×Ô¼ºµÄ·½Ê½À´ÃèÊöÕâЩ¸ÅÄîÒÔÊÊÓ¦±¾ÎÄ¡£Çø±ð¾ÍÊDz»Í¬µÄ×é¼þ£¬×ÜÌå˼·Ϊ£ºÊý¾Ý¿âÊÇÓɶàÖÖ»¥Ïཻ»¥µÄ×é¼þ¹¹³ÉµÄ¡£

ºËÐÄ×é¼þ£º

½ø³Ì¹ÜÀíÆ÷£¨process manager£©£ººÜ¶àÊý¾Ý¿â¾ß±¸Ò»¸öÐèÒªÍ×ÉÆ¹ÜÀíµÄ½ø³Ì/Ï̳߳ء£ÔÙÕߣ¬ÎªÁËʵÏÖÄÉÃë¼¶²Ù×÷£¬Ò»Ð©ÏÖ´úÊý¾Ý¿âʹÓÃ×Ô¼ºµÄÏ̶߳ø²»ÊDzÙ×÷ϵͳÏ̡߳£

ÍøÂç¹ÜÀíÆ÷£¨network manager£©£ºÍøÂ·I/OÊǸö´óÎÊÌ⣬ÓÈÆäÊǶÔÓÚ·Ö²¼Ê½Êý¾Ý¿â¡£ËùÒÔһЩÊý¾Ý¿â¾ß±¸×Ô¼ºµÄÍøÂç¹ÜÀíÆ÷¡£

Îļþϵͳ¹ÜÀíÆ÷£¨File system manager£©£º´ÅÅÌI/OÊÇÊý¾Ý¿âµÄÊ×Ҫƿ¾±¡£¾ß±¸Ò»¸öÎļþϵͳ¹ÜÀíÆ÷À´ÍêÃÀµØ´¦ÀíOSÎļþϵͳÉõÖÁÈ¡´úOSÎļþϵͳ£¬ÊǷdz£ÖØÒªµÄ¡£

ÄÚ´æ¹ÜÀíÆ÷£¨memory manager£©£ºÎªÁ˱ÜÃâ´ÅÅÌI/O´øÀ´µÄÐÔÄÜËðʧ£¬ÐèÒª´óÁ¿µÄÄÚ´æ¡£µ«ÊÇÈç¹ûÄãÒª´¦Àí´óÈÝÁ¿ÄÚ´æÄãÐèÒª¸ßЧµÄÄÚ´æ¹ÜÀíÆ÷£¬ÓÈÆäÊÇÄãÓкܶà²éѯͬʱʹÓÃÄÚ´æµÄʱºò¡£

°²È«¹ÜÀíÆ÷£¨Security Manager£©£ºÓÃÓÚ¶ÔÓû§µÄÑéÖ¤ºÍÊÚȨ¡£

¿Í»§¶Ë¹ÜÀíÆ÷£¨Client manager£©£ºÓÃÓÚ¹ÜÀí¿Í»§¶ËÁ¬½Ó¡£

¡­¡­

¹¤¾ß£º

±¸·Ý¹ÜÀíÆ÷£¨Backup manager£©£ºÓÃÓÚ±£´æºÍ»Ö¸´Êý¾Ý¡£

¸´Ô­¹ÜÀíÆ÷£¨Recovery manager£©£ºÓÃÓÚ±ÀÀ£ºóÖØÆôÊý¾Ý¿âµ½Ò»¸öÒ»ÖÂ״̬¡£

¼à¿Ø¹ÜÀíÆ÷£¨Monitor manager£©£ºÓÃÓڼǼÊý¾Ý¿â»î¶¯ÐÅÏ¢ºÍÌṩ¼à¿ØÊý¾Ý¿âµÄ¹¤¾ß¡£

Administration¹ÜÀíÆ÷£¨Administration manager£©£ºÓÃÓÚ±£´æÔªÊý¾Ý£¨±ÈÈç±íµÄÃû³ÆºÍ½á¹¹£©£¬Ìṩ¹ÜÀíÊý¾Ý¿â¡¢Ä£Ê½¡¢±í¿Õ¼äµÄ¹¤¾ß¡£¡¾ÒëÕß×¢£ººÃ°É£¬ÎÒÕæµÄ²»ÖªµÀAdministration manager¸Ã·­Òë³Éʲô£¬ÓÐÖªµÀµÄÂé·³¸æÖª£¬²»Ê¤¸Ð¼¤¡­¡­¡¿

¡­¡­

²éѯ¹ÜÀíÆ÷£º

²éѯ½âÎöÆ÷£¨Query parser£©£ºÓÃÓÚ¼ì²é²éѯÊÇ·ñºÏ·¨

²éÑ¯ÖØÐ´Æ÷£¨Query rewriter£©£ºÓÃÓÚÔ¤ÓÅ»¯²éѯ

²éѯÓÅ»¯Æ÷£¨Query optimizer£©£ºÓÃÓÚÓÅ»¯²éѯ

²éѯִÐÐÆ÷£¨Query executor£©£ºÓÃÓÚ±àÒëºÍÖ´Ðвéѯ

Êý¾Ý¹ÜÀíÆ÷£º

ÊÂÎñ¹ÜÀíÆ÷£¨Transaction manager£©£ºÓÃÓÚ´¦ÀíÊÂÎñ

»º´æ¹ÜÀíÆ÷£¨Cache manager£©£ºÊý¾Ý±»Ê¹ÓÃ֮ǰÖÃÓÚÄڴ棬»òÕßÊý¾ÝдÈë´ÅÅÌ֮ǰÖÃÓÚÄÚ´æ

Êý¾Ý·ÃÎʹÜÀíÆ÷£¨Data access manager£©£º·ÃÎÊ´ÅÅÌÖеÄÊý¾Ý

ÔÚ±¾ÎÄÊ£Óಿ·Ö£¬ÎһἯÖÐ̽ÌÖÊý¾Ý¿âÈçºÎͨ¹ýÈçϽø³Ì¹ÜÀíSQL²éѯµÄ£º

¿Í»§¶Ë¹ÜÀíÆ÷

²éѯ¹ÜÀíÆ÷

Êý¾Ý¹ÜÀíÆ÷£¨º¬¸´Ô­¹ÜÀíÆ÷£©

¿Í»§¶Ë¹ÜÀíÆ÷

¿Í»§¶Ë¹ÜÀíÆ÷ÊÇ´¦Àí¿Í»§¶ËͨÐŵġ£¿Í»§¶Ë¿ÉÒÔÊÇÒ»¸ö£¨ÍøÕ¾£©·þÎñÆ÷»òÕßÒ»¸ö×îÖÕÓû§»ò×îÖÕÓ¦Ó᣿ͻ§¶Ë¹ÜÀíÆ÷ͨ¹ýһϵÁÐÖªÃûµÄAPI£¨JDBC, ODBC, OLE-DB ¡­£©Ìṩ²»Í¬µÄ·½Ê½À´·ÃÎÊÊý¾Ý¿â¡£

¿Í»§¶Ë¹ÜÀíÆ÷Ò²ÌṩרÓеÄÊý¾Ý¿â·ÃÎÊAPI¡£

µ±ÄãÁ¬½Óµ½Êý¾Ý¿âʱ£º

¹ÜÀíÆ÷Ê×Ïȼì²éÄãµÄÑéÖ¤ÐÅÏ¢£¨Óû§ÃûºÍÃÜÂ룩£¬È»ºó¼ì²éÄãÊÇ·ñÓзÃÎÊÊý¾Ý¿âµÄÊÚȨ¡£ÕâЩȨÏÞÓÉDBA·ÖÅä¡£

È»ºó£¬¹ÜÀíÆ÷¼ì²éÊÇ·ñÓпÕÏнø³Ì£¨»òỊ̈߳©À´´¦ÀíÄã¶Ô²éѯ¡£

¹ÜÀíÆ÷»¹»á¼ì²éÊý¾Ý¿âÊÇ·ñ¸ºÔغÜÖØ¡£

¹ÜÀíÆ÷¿ÉÄÜ»áµÈ´ýÒ»»á¶ùÀ´»ñÈ¡ÐèÒªµÄ×ÊÔ´¡£Èç¹ûµÈ´ýʱ¼ä´ïµ½³¬Ê±Ê±¼ä£¬Ëü»á¹Ø±ÕÁ¬½Ó²¢¸ø³öÒ»¸ö¿É¶ÁµÄ´íÎóÐÅÏ¢¡£

È»ºó¹ÜÀíÆ÷»á°ÑÄãµÄ²éѯË͸ø²éѯ¹ÜÀíÆ÷À´´¦Àí¡£

ÒòΪ²éѯ´¦Àí½ø³Ì²»ÊÇ¡º²»È«ÔòÎÞ¡»µÄ£¬Ò»µ©Ëü´Ó²éѯ¹ÜÀíÆ÷µÃµ½Êý¾Ý£¬Ëü»á°Ñ²¿·Ö½á¹û±£´æµ½Ò»¸ö»º³åÇø²¢ÇÒ¿ªÊ¼¸øÄã·¢ËÍ¡£

Èç¹ûÓöµ½ÎÊÌ⣬¹ÜÀíÆ÷¹Ø±ÕÁ¬½Ó£¬ÏòÄã·¢ËͿɶÁµÄ½âÊÍÐÅÏ¢£¬È»ºóÊÍ·Å×ÊÔ´¡£

²éѯ¹ÜÀíÆ÷

Õⲿ·ÖÊÇÊý¾Ý¿âµÄÍþÁ¦ËùÔÚ£¬ÔÚÕⲿ·ÖÀһ¸öдµÃÔã¸âµÄ²éѯ¿ÉÒÔת»»³ÉÒ»¸ö¿ìËÙÖ´ÐеĴúÂ룬´úÂëÖ´ÐеĽá¹û±»Ë͵½¿Í»§¶Ë¹ÜÀíÆ÷¡£Õâ¸ö¶à²½Öè²Ù×÷¹ý³ÌÈçÏ£º

²éѯÊ×Ïȱ»½âÎö²¢ÅжÏÊÇ·ñºÏ·¨

È»ºó±»ÖØÐ´£¬È¥³ýÁËÎÞÓõIJÙ×÷²¢ÇÒ¼ÓÈëÔ¤ÓÅ»¯²¿·Ö

½Ó×ű»ÓÅ»¯ÒÔ±ãÌáÉýÐÔÄÜ£¬²¢±»×ª»»Îª¿ÉÖ´ÐдúÂëºÍÊý¾Ý·ÃÎʼƻ®¡£

È»ºó¼Æ»®±»±àÒë

×îºó£¬±»Ö´ÐÐ

ÕâÀïÎÒ²»»á¹ý¶à̽ÌÖ×îºóÁ½²½£¬ÒòΪËüÃDz»Ì«ÖØÒª¡£

²éѯ½âÎöÆ÷

ÿһÌõSQLÓï¾ä¶¼ÒªË͵½½âÎöÆ÷À´¼ì²éÓï·¨£¬Èç¹ûÄãµÄ²éѯÓÐ´í£¬½âÎöÆ÷½«¾Ü¾ø¸Ã²éѯ¡£±ÈÈ磬Èç¹ûÄãд³É¡±SLECT ¡­¡± ¶ø²»ÊÇ ¡°SELECT ¡­¡±£¬ÄǾÍûÓÐÏÂÎÄÁË¡£

µ«Õ⻹²»ËãÍ꣬½âÎöÆ÷»¹»á¼ì²é¹Ø¼ü×ÖÊÇ·ñʹÓÃÕýÈ·µÄ˳Ðò£¬±ÈÈç WHERE дÔÚ SELECT ֮ǰ»á±»¾Ü¾ø¡£

È»ºó£¬½âÎöÆ÷Òª·ÖÎö²éѯÖеıíºÍ×ֶΣ¬Ê¹ÓÃÊý¾Ý¿âÔªÊý¾ÝÀ´¼ì²é£º

±íÊÇ·ñ´æÔÚ

±íµÄ×Ö¶ÎÊÇ·ñ´æÔÚ

¶ÔijÀàÐÍ×Ö¶ÎµÄ ÔËËã ÊÇ·ñ ¿ÉÄÜ£¨±ÈÈ磬Äã²»Äܽ«ÕûÊýºÍ×Ö·û´®½øÐбȽϣ¬Äã²»ÄܶÔÒ»¸öÕûÊýʹÓà substring() º¯Êý£©

½Ó×Å£¬½âÎöÆ÷¼ì²éÔÚ²éѯÖÐÄãÊÇ·ñÓÐȨÏÞÀ´¶ÁÈ¡£¨»òдÈ룩±í¡£ÔÙÇ¿µ÷Ò»´Î£ºÕâЩȨÏÞÓÉDBA·ÖÅä¡£

ÔÚ½âÎö¹ý³ÌÖУ¬SQL ²éѯ±»×ª»»ÎªÄÚ²¿±íʾ£¨Í¨³£ÊÇÒ»¸öÊ÷£©¡£

Èç¹ûÒ»ÇÐÕý³££¬ÄÚ²¿±íʾ±»Ë͵½²éÑ¯ÖØÐ´Æ÷¡£

²éÑ¯ÖØÐ´Æ÷

ÔÚÕâÒ»²½£¬ÎÒÃÇÒѾ­ÓÐÁ˲éѯµÄÄÚ²¿±íʾ£¬ÖØÐ´Æ÷µÄÄ¿±êÊÇ£º

Ô¤ÓÅ»¯²éѯ

±ÜÃâ²»±ØÒªµÄÔËËã

°ïÖúÓÅ»¯Æ÷ÕÒµ½ºÏÀíµÄ×î¼Ñ½â¾ö·½°¸

ÖØÐ´Æ÷°´ÕÕһϵÁÐÒÑÖªµÄ¹æÔò¶Ô²éѯִÐмì²â¡£Èç¹û²éѯƥÅäÒ»ÖÖģʽµÄ¹æÔò£¬²éѯ¾Í»á°´ÕÕÕâÌõ¹æÔòÀ´ÖØÐ´¡£ÏÂÃæÊÇ£¨¿ÉÑ¡£©¹æÔòµÄ·ÇÏ꾡µÄÁÐ±í£º

ÊÓͼºÏ²¢£ºÈç¹ûÄãÔÚ²éѯÖÐʹÓÃÊÓͼ£¬ÊÓͼ¾Í»áת»»ÎªËüµÄ SQL ´úÂë¡£

×Ó²éѯ±âƽ»¯£º×Ó²éѯÊǺÜÄÑÓÅ»¯µÄ£¬Òò´ËÖØÐ´Æ÷»á³¢ÊÔÒÆ³ý×Ó²éѯ

ÀýÈ磺

Hello World!

»áת»»Îª£º

Hello World!

È¥³ý²»±ØÒªµÄÔËËã·û£º±ÈÈ磬Èç¹ûÄãÓÃÁË DISTINCT£¬¶øÆäʵÄãÓÐ UNIQUE Ô¼Êø£¨Õâ±¾Éí¾Í·ÀÖ¹ÁËÊý¾Ý³öÏÖÖØ¸´£©£¬ÄÇô DISTINCT ¹Ø¼ü×־ͱ»È¥µôÁË¡£

ÅųýÈßÓàµÄÁª½Ó£ºÈç¹ûÏàͬµÄ JOIN Ìõ¼þ³öÏÖÁ½´Î£¬±ÈÈçÒþ²ØÔÚÊÓͼÖÐµÄ JOIN Ìõ¼þ£¬»òÕßÓÉÓÚ´«µÝÐÔ²úÉúµÄÎÞÓà JOIN£¬¶¼»á±»Ïû³ý¡£

³£Êý¼ÆË㸳ֵ£ºÈç¹ûÄãµÄ²éѯÐèÒª¼ÆË㣬ÄÇôÔÚÖØÐ´¹ý³ÌÖмÆËã»áÖ´ÐÐÒ»´Î¡£±ÈÈç WHERE AGE > 10+2 »áת»»Îª WHERE AGE > 12 £¬ TODATE(¡°ÈÕÆÚ×Ö·û´®¡±) »áת»»Îª datetime ¸ñʽµÄÈÕÆÚÖµ¡£

£¨¸ß¼¶£©·ÖÇø²Ã¼ô£¨Partition Pruning£©£ºÈç¹ûÄãÓÃÁË·ÖÇø±í£¬ÖØÐ´Æ÷Äܹ»ÕÒµ½ÐèҪʹÓõķÖÇø¡£

£¨¸ß¼¶£©ÎﻯÊÓÍ¼ÖØÐ´£¨Materialized view rewrite£©£ºÈç¹ûÄãÓиöÎﻯÊÓͼƥÅä²éѯν´ÊµÄÒ»¸ö×Ó¼¯£¬ÖØÐ´Æ÷½«¼ì²éÊÓͼÊÇ·ñ×îв¢Ð޸IJéѯ£¬Áî²éѯʹÓÃÎﻯÊÓͼ¶ø²»ÊÇԭʼ±í¡£

£¨¸ß¼¶£©×Ô¶¨Ò广Ôò£ºÈç¹ûÄãÓÐ×Ô¶¨Ò广ÔòÀ´Ð޸IJéѯ£¨¾ÍÏñ Oracle policy£©£¬ÖØÐ´Æ÷¾Í»áÖ´ÐÐÕâЩ¹æÔò¡£

£¨¸ß¼¶£©OLAPת»»£º·ÖÎö/¼Ó´° º¯Êý£¬ÐÇÐÎÁª½Ó£¬ROLLUP º¯Êý¡­¡­¶¼»á·¢Éúת»»£¨µ«ÎÒ²»È·¶¨ÕâÊÇÓÉÖØÐ´Æ÷»¹ÊÇÓÅ»¯Æ÷À´Íê³É£¬ÒòΪÁ½¸ö½ø³ÌÁªÏµºÜ½ô£¬±ØÐë¿´ÊÇʲôÊý¾Ý¿â£©¡£

¡¾ÒëÕß×¢£º ÎﻯÊÓͼ ¡£Î½´Ê£¬predicate£¬Ìõ¼þ±í´ïʽµÄÇóÖµ·µ»ØÕæ»ò¼ÙµÄ¹ý³Ì¡¿

ÖØÐ´ºóµÄ²éѯ½Ó×ÅË͵½ÓÅ»¯Æ÷£¬ÕâʱºòºÃÍæµÄ¾Í¿ªÊ¼ÁË¡£

ͳ¼Æ

Ñо¿Êý¾Ý¿âÈçºÎÓÅ»¯²éѯ֮ǰÎÒÃÇÐèҪ̸̸ͳ¼Æ£¬ÒòΪûÓÐͳ¼ÆµÄÊý¾Ý¿âÊÇÓÞ´ÀµÄ¡£³ý·ÇÄãÃ÷ȷָʾ£¬Êý¾Ý¿âÊDz»»á·ÖÎö×Ô¼ºµÄÊý¾ÝµÄ¡£Ã»ÓзÖÎö»áµ¼ÖÂÊý¾Ý¿â×ö³ö£¨·Ç³££©Ôã¸âµÄ¼ÙÉè¡£

µ«ÊÇ£¬Êý¾Ý¿âÐèҪʲôÀàÐ͵ÄÐÅÏ¢ÄØ£¿

ÎÒ±ØÐ루¼òÒªµØ£©Ì¸Ì¸Êý¾Ý¿âºÍ²Ù×÷ϵͳÈçºÎ±£´æÊý¾Ý¡£Á½ÕßʹÓõÄ×îСµ¥Î»½Ð×öÒ³»ò¿é£¨Ä¬ÈÏ 4 »ò 8 KB£©¡£Õâ¾ÍÊÇ˵Èç¹ûÄã½öÐèÒª 1KB£¬Ò²»áÕ¼ÓÃÒ»¸öÒ³¡£ÒªÊÇÒ³µÄ´óСΪ 8KB£¬Äã¾ÍÀË·ÑÁË 7KB¡£

»ØÀ´¼ÌÐø½²Í³¼Æ£¡ µ±ÄãÒªÇóÊý¾Ý¿âÊÕ¼¯Í³¼ÆÐÅÏ¢£¬Êý¾Ý¿â»á¼ÆËãÏÂÁÐÖµ£º

±íÖÐÐкÍÒ³µÄÊýÁ¿

±íÖÐÿ¸öÁÐÖеģº

Ψһֵ

Êý¾Ý³¤¶È£¨×îС£¬×î´ó£¬Æ½¾ù£©

Êý¾Ý·¶Î§£¨×îС£¬×î´ó£¬Æ½¾ù£©

±íµÄË÷ÒýÐÅÏ¢

ÕâЩͳ¼ÆÐÅÏ¢»á°ïÖúÓÅ»¯Æ÷¹À¼Æ²éѯËùÐèµÄ´ÅÅÌ I/O¡¢CPU¡¢ºÍÄÚ´æÊ¹ÓÃ

¶Ôÿ¸öÁеÄͳ¼Æ·Ç³£ÖØÒª¡£

±ÈÈ磬Èç¹ûÒ»¸ö±í PERSON ÐèÒªÁª½Ó 2 ¸öÁУº LAST_NAME, FIRST_NAME¡£

¸ù¾Ýͳ¼ÆÐÅÏ¢£¬Êý¾Ý¿âÖªµÀFIRST_NAMEÖ»ÓÐ 1,000 ¸ö²»Í¬µÄÖµ£¬LAST_NAME ÓÐ 1,000,000 ¸ö²»Í¬µÄÖµ¡£

Òò´Ë£¬Êý¾Ý¿â¾Í»á°´ÕÕ LAST_NAME, FIRST_NAME Áª½Ó¡£

ÒòΪ LAST_NAME ²»´ó¿ÉÄÜÖØ¸´£¬¶àÊýÇé¿öÏÂ±È½Ï LAST_NAME µÄÍ· 2 ¡¢ 3 ¸ö×Ö·û¾Í¹»ÁË£¬Õ⽫´ó´ó¼õÉٱȽϵĴÎÊý¡£

²»¹ý£¬ÕâЩֻÊÇ»ù±¾µÄͳ¼Æ¡£Äã¿ÉÒÔÈÃÊý¾Ý¿â×öÒ»Öָ߼¶Í³¼Æ£¬½ÐÖ±·½Í¼¡£Ö±·½Í¼ÊÇÁÐÖµ·Ö²¼Çé¿öµÄͳ¼ÆÐÅÏ¢¡£ÀýÈ磺

³öÏÖ×îÆµ·±µÄÖµ

·ÖλÊý ¡¾ÒëÕß×¢£ºhttp://baike.baidu.com/view/1323572.htm¡¿

¡­

ÕâЩ¶îÍâµÄͳ¼Æ»á°ïÖúÊý¾Ý¿âÕÒµ½¸ü¼ÑµÄ²éѯ¼Æ»®£¬ÓÈÆäÊǶÔÓÚµÈʽν´Ê£¨ÀýÈ磺 WHERE AGE = 18 £©»ò·¶Î§Î½´Ê£¨ÀýÈ磺 WHERE AGE > 10 and AGE < 40£©£¬ÒòΪÊý¾Ý¿â¿ÉÒÔ¸üºÃµÄÁ˽âÕâЩν´ÊÏà¹ØµÄÊý×ÖÀàÐÍÊý¾ÝÐУ¨×¢£ºÕâ¸ö¸ÅÄîµÄ¼¼ÊõÃû³Æ½ÐÑ¡ÔñÂÊ£©¡£

ͳ¼ÆÐÅÏ¢±£´æÔÚÊý¾Ý¿âÔªÊý¾ÝÄÚ£¬ÀýÈ磨·Ç·ÖÇø£©±íµÄͳ¼ÆÐÅϢλÖãº

Oracle£º USER / ALL / DBA_TABLES ºÍ USER / ALL / DBA_TAB_COLUMNS

DB2£º SYSCAT.TABLES ºÍ SYSCAT.COLUMNS

ͳ¼ÆÐÅÏ¢±ØÐ뼰ʱ¸üС£Èç¹ûÒ»¸ö±íÓÐ 1,000,000 ÐжøÊý¾Ý¿âÈÏΪËüÖ»ÓÐ 500 ÐУ¬Ã»ÓбÈÕâ¸üÔã¸âµÄÁË¡£Í³¼ÆÎ¨Ò»µÄ²»ÀûÖ®´¦ÊÇÐèҪʱ¼äÀ´¼ÆË㣬Õâ¾ÍÊÇΪʲôÊý¾Ý¿â´ó¶àĬÈÏÇé¿öϲ»»á×Ô¶¯¼ÆËãͳ¼ÆÐÅÏ¢¡£Êý¾Ý´ïµ½°ÙÍò¼¶Ê±Í³¼Æ»á±äµÃÀ§ÄÑ£¬Õâʱºò£¬Äã¿ÉÒÔÑ¡Ôñ½ö×ö»ù±¾Í³¼Æ»òÕßÔÚÒ»¸öÊý¾Ý¿âÑù±¾ÉÏÖ´ÐÐͳ¼Æ¡£

¾Ù¸öÀý×Ó£¬ÎÒ²ÎÓëµÄÒ»¸öÏîÄ¿ÐèÒª´¦Àíÿ±íÉÏÒÚÌõÊý¾ÝµÄ¿â£¬ÎÒÑ¡Ôñֻͳ¼Æ10%£¬½á¹ûÔì³ÉÁ˾޴óµÄʱ¼äÏûºÄ¡£±¾ÀýÖ¤Ã÷ÕâÊǸöÔã¸âµÄ¾ö¶¨£¬ÒòΪÓÐʱºò Oracle 10G ´ÓÌØ¶¨±íµÄÌØ¶¨ÁÐÖÐÑ¡³öµÄ 10% ¸úÈ«²¿ 100% Óкܴó²»Í¬£¨¶ÔÓÚÓµÓÐÒ»ÒÚÐÐÊý¾ÝµÄ±í£¬ÕâÖÖÇé¿ö¼«ÉÙ·¢Éú£©¡£Õâ´Î´íÎóµÄͳ¼Æµ¼ÖÂÁËÒ»¸ö±¾Ó¦ 30 ÃëÍê³ÉµÄ²éѯ×îºóÖ´ÐÐÁË 8 ¸öСʱ£¬²éÕÒÕâ¸öÏÖÏó¸ùÔ´µÄ¹ý³Ì¼òÖ±ÊǸöجÃΡ£Õâ¸öÀý×ÓÏÔʾÁËͳ¼ÆµÄÖØÒªÐÔ¡£

×¢£ºµ±È»ÁË£¬Ã¿¸öÊý¾Ý¿â»¹ÓÐÆäÌØ¶¨µÄ¸ü¸ß¼¶µÄͳ¼Æ¡£Èç¹ûÄãÏëÁ˽â¸ü¶àÐÅÏ¢£¬¶Á¶ÁÊý¾Ý¿âµÄÎĵµ¡£»°ËäÈ»Õâô˵£¬ÎÒÒѾ­¾¡Á¦Àí½âͳ¼ÆÊÇÈçºÎʹÓõÄÁË£¬¶øÇÒÎÒÕÒµ½µÄ×îºÃµÄ¹Ù·½ÎĵµÀ´×ÔPostgreSQL¡£

²éѯÓÅ»¯Æ÷

ËùÓеÄÏÖ´úÊý¾Ý¿â¶¼ÔÚÓûùÓڳɱ¾µÄÓÅ»¯£¨¼´CBO£©À´ÓÅ»¯²éѯ¡£µÀÀíÊÇÕë¶Ôÿ¸öÔËËãÉèÖÃÒ»¸ö³É±¾£¬Í¨¹ýÓ¦Óóɱ¾×îµÍÁ®µÄһϵÁÐÔËË㣬À´ÕÒµ½×î¼ÑµÄ½µµÍ²éѯ³É±¾µÄ·½·¨¡£

ΪÁËÀí½â³É±¾ÓÅ»¯Æ÷µÄÔ­Àí£¬ÎÒ¾õµÃ×îºÃÓøöÀý×ÓÀ´¡º¸ÐÊÜ¡»Ò»ÏÂÕâ¸öÈÎÎñ±³ºóµÄ¸´ÔÓÐÔ¡£ÕâÀïÎÒ½«¸ø³öÁª½Ó 2 ¸ö±íµÄ 3 ¸ö·½·¨£¬ÎÒÃǺܿì¾ÍÄÜ¿´µ½¼´±ãÒ»¸ö¼òµ¥µÄÁª½Ó²éѯ¶ÔÓÚÓÅ»¯Æ÷À´Ëµ¶¼ÊǸöجÃΡ£Ö®ºó£¬ÎÒÃÇ»áÁ˽âÕæÕýµÄÓÅ»¯Æ÷ÊÇÔõô×öµÄ¡£

¶ÔÓÚÕâЩÁª½Ó²Ù×÷£¬ÎÒ»áרעÓÚËüÃǵÄʱ¼ä¸´ÔÓ¶È£¬µ«ÊÇ£¬Êý¾Ý¿âÓÅ»¯Æ÷¼ÆËãµÄÊÇËüÃÇµÄ CPU ³É±¾¡¢´ÅÅÌ I/O ³É±¾¡¢ºÍÄÚ´æÐèÇó¡£Ê±¼ä¸´ÔÓ¶ÈºÍ CPU ³É±¾µÄÇø±ðÊÇ£¬Ê±¼ä³É±¾ÊǸö½üËÆÖµ£¨¸øÎÒÕâÑùµÄÀÁ¼Ò»ï×¼±¸µÄ£©¡£¶ø CPU ³É±¾£¬ÎÒÕâÀï°üÀ¨ÁËËùÓеÄÔËË㣬±ÈÈ磺¼Ó·¨¡¢Ìõ¼þÅжϡ¢³Ë·¨¡¢µü´ú¡­¡­»¹ÓÐÄØ£º

ÿһ¸ö¸ß¼¶´úÂëÔËËã¶¼ÒªÌØ¶¨ÊýÁ¿µÄµÍ¼¶ CPU ÔËËã¡£

¶ÔÓÚ Intel Core i7¡¢Intel Pentium 4¡¢AMD Opteron¡­µÈ£¬£¨¾Í CPU ÖÜÆÚ¶øÑÔ£©CPU µÄÔËËã³É±¾ÊDz»Í¬µÄ£¬Ò²¾ÍÊÇ˵ËüÈ¡¾öÓÚ CPU µÄ¼Ü¹¹¡£

ʹÓÃʱ¼ä¸´ÔӶȾÍÈÝÒ×¶àÁË£¨ÖÁÉÙ¶ÔÎÒÀ´Ëµ£©£¬ÓÃËüÎÒÒ²ÄÜÁ˽⵽ CBO µÄ¸ÅÄî¡£ÓÉÓÚ´ÅÅÌ I/O ÊǸöÖØÒªµÄ¸ÅÄÎÒż¶ûÒ²»áÌáµ½Ëü¡£ÇëÀμǣ¬´ó¶àÊýʱºòÆ¿¾±ÔÚÓÚ´ÅÅÌ I/O ¶ø²»ÊÇ CPU ʹÓá£

Ë÷Òý

ÔÚÑо¿ B+Ê÷µÄʱºòÎÒÃÇ̸µ½ÁËË÷Òý£¬Òª¼Çסһµã£¬Ë÷Òý¶¼ÊÇÒѾ­ÅÅÁËÐòµÄ¡£

½ö¹©²Î¿¼£º»¹ÓÐÆäËûÀàÐ͵ÄË÷Òý£¬±ÈÈçλͼË÷Òý£¬ÔÚ CPU¡¢´ÅÅÌI/O¡¢ºÍÄÚ´æ·½ÃæÓëB+Ê÷Ë÷ÒýµÄ³É±¾²¢²»Ïàͬ¡£

ÁíÍ⣬ºÜ¶àÏÖ´úÊý¾Ý¿âΪÁ˸ÄÉÆÖ´Ðмƻ®µÄ³É±¾£¬¿ÉÒÔ½öΪµ±Ç°²éѯ¶¯Ì¬µØÉú³ÉÁÙʱË÷Òý¡£

´æÈ¡Â·¾¶

ÔÚÓ¦ÓÃÁª½ÓÔËËã·û£¨join operators£©Ö®Ç°£¬ÄãÊ×ÏÈÐèÒª»ñµÃÊý¾Ý¡£ÒÔϾÍÊÇ»ñµÃÊý¾ÝµÄ·½·¨¡£

×¢£ºÓÉÓÚËùÓдæÈ¡Â·¾¶µÄÕæÕýÎÊÌâÊÇ´ÅÅÌ I/O£¬ÎÒ²»»á¹ý¶à̽ÌÖʱ¼ä¸´ÔÓ¶È¡£

¡¾ÒëÕß×¢£ºËÄÖÖÀàÐ͵ÄOracleË÷ÒýɨÃè½éÉÜ ¡¿

ȫɨÃè

Èç¹ûÄã¶Á¹ýÖ´Ðмƻ®£¬Ò»¶¨¿´µ½¹ý¡ºÈ«É¨Ãè¡»£¨»òÖ»ÊÇ¡ºÉ¨Ãè¡»£©Ò»´Ê¡£¼òµ¥µÄ˵ȫɨÃè¾ÍÊÇÊý¾Ý¿âÍêÕûµÄ¶ÁÒ»¸ö±í»òË÷Òý¡£¾Í´ÅÅÌ I/O ¶øÑÔ£¬ºÜÃ÷ÏÔÈ«±íɨÃèµÄ³É±¾±ÈË÷ÒýȫɨÃèÒª¸ß°º¡£

·¶Î§É¨Ãè

ÆäËûÀàÐ͵ÄɨÃèÓÐË÷Òý·¶Î§É¨Ã裬±ÈÈçµ±ÄãʹÓÃν´Ê ¡± WHERE AGE > 20 AND AGE < 40 ¡± µÄʱºòËü¾Í»á·¢Éú¡£

µ±È»£¬ÄãÐèÒªÔÚ AGE ×Ö¶ÎÉÏÓÐË÷Òý²ÅÄÜÓõ½Ë÷Òý·¶Î§É¨Ãè¡£

ÔÚµÚÒ»²¿·ÖÎÒÃÇÒѾ­ÖªµÀ£¬·¶Î§²éѯµÄʱ¼ä³É±¾´óÔ¼ÊÇ log(N)+M£¬ÕâÀï N ÊÇË÷ÒýµÄÊý¾ÝÁ¿£¬M ÊÇ·¶Î§ÄÚ¹À²âµÄÐÐÊý¡£¶à¿÷ÓÐÁËͳ¼ÆÎÒÃDzÅÄÜÖªµÀ N ºÍ M µÄÖµ£¨×¢£º M ÊÇν´Ê ¡° AGE > 20 AND AGE < 40 ¡± µÄÑ¡ÔñÂÊ£©¡£ÁíÍⷶΧɨÃèʱ£¬Äã²»ÐèÒª¶ÁÈ¡Õû¸öË÷Òý£¬Òò´ËÔÚ´ÅÅÌ I/O ·½ÃæÃ»ÓÐȫɨÃèÄÇô°º¹ó¡£

ΨһɨÃè

Èç¹ûÄãÖ»ÐèÒª´ÓË÷ÒýÖÐȡһ¸öÖµÄã¿ÉÒÔÓÃΨһɨÃè¡£

¸ù¾Ý ROW ID ´æÈ¡

¶àÊýÇé¿öÏ£¬Èç¹ûÊý¾Ý¿âʹÓÃË÷Òý£¬Ëü¾Í±ØÐë²éÕÒÓëË÷ÒýÏà¹ØµÄÐУ¬ÕâÑù¾Í»áÓõ½¸ù¾Ý ROW ID ´æÈ¡µÄ·½Ê½¡£

ÀýÈ磬¼ÙÈçÄãÔËÐУº

SELECT LASTNAME, FIRSTNAME from PERSON WHERE AGE = 28

Èç¹û person ±íµÄ age ÁÐÓÐË÷Òý£¬ÓÅ»¯Æ÷»áʹÓÃË÷ÒýÕÒµ½ËùÓÐÄêÁäΪ 28 µÄÈË£¬È»ºóËü»áÈ¥±íÖжÁÈ¡Ïà¹ØµÄÐУ¬ÕâÊÇÒòΪË÷ÒýÖÐÖ»ÓÐ age µÄÐÅÏ¢¶øÄãÒªµÄÊÇÐÕºÍÃû¡£

µ«ÊÇ£¬¼ÙÈçÄã»»¸ö×ö·¨£º

SELECT TYPE_PERSON.CATEGORY from PERSON ,TYPE_PERSON
WHERE PERSON.AGE = TYPE_PERSON.AGE

PERSON ±íµÄË÷Òý»áÓÃÀ´Áª½Ó TYPE_PERSON ±í£¬µ«ÊÇ PERSON ±í²»»á¸ù¾ÝÐÐID ´æÈ¡£¬ÒòΪÄ㲢ûÓÐÒªÇóÕâ¸ö±íÄÚµÄÐÅÏ¢¡£

ËäÈ»Õâ¸ö·½·¨ÔÚÉÙÁ¿´æÈ¡Ê±±íÏֺܺã¬Õâ¸öÔËËãµÄÕæÕýÎÊÌâÆäʵÊÇ´ÅÅÌ I/O¡£¼ÙÈçÐèÒª´óÁ¿µÄ¸ù¾ÝÐÐID´æÈ¡£¬Êý¾Ý¿âÒ²Ðí»áÑ¡ÔñȫɨÃè¡£

ÆäËü·¾¶

ÎÒûÓÐÁоÙËùÓеĴæÈ¡Â·¾¶£¬Èç¹ûÄã¸ÐÐËȤ¿ÉÒÔ¶ÁÒ»¶Á OracleÎĵµ¡£ÆäËüÊý¾Ý¿âÀïÒ²Ðí½Ð·¨²»Í¬µ«±³ºóµÄ¸ÅÄîÊÇÒ»ÑùµÄ¡£

Áª½ÓÔËËã·û

ÄÇô£¬ÎÒÃÇÖªµÀÈçºÎ»ñÈ¡Êý¾ÝÁË£¬ÄÇÏÖÔھͰÑËüÃÇÁª½ÓÆðÀ´£¡

ÎÒÒªÕ¹ÏÖµÄÊÇ3¸ö¸ö³£ÓÃÁª½ÓÔËËã·û£ººÏ²¢Áª½Ó£¨Merge join£©£¬¹þÏ£Áª½Ó£¨Hash Join£©ºÍǶÌ×Ñ­»·Áª½Ó£¨Nested Loop Join£©¡£µ«ÊÇÔÚ´Ë֮ǰ£¬ÎÒÐèÒªÒýÈëдʻãÁË£ºÄÚ¹ØÏµºÍÍâ¹ØÏµ£¨ inner relation and outer relation£© ¡¾ÒëÕß×¢£º ¡°ÄÚ¹ØÏµºÍÍâ¹ØÏµ¡± Õâ¸ö˵·¨À´Ô´²»Ã÷£¬¸ú²éѯµÄ¡°ÄÚÁª½Ó£¨INNER JOIN£© ¡¢ÍâÁª½Ó£¨OUTER JOIN£© ¡± ²»ÊÇÒ»¸ö¸ÅÄî ¡£Ö»²éµ½°Ù¶È°Ù¿Æ´ÊÌõ£º¹ØÏµÊý¾Ý¿â ÀïÌáµ½¡°Ã¿¸ö±í¸ñ£¨ÓÐʱ±»³ÆÎªÒ»¸ö¹ØÏµ£©¡­¡­¡± ¡£ ÆäËû²Î¿¼Á´½Ó ¡°Merge Join¡± ¡°Hash Join¡± ¡°Nested Loop Join¡± ¡¿ ¡£ Ò»¸ö¹ØÏµ¿ÉÒÔÊÇ£º

Ò»¸ö±í

Ò»¸öË÷Òý

ÉÏÒ»¸öÔËËãµÄÖмä½á¹û£¨±ÈÈçÉÏÒ»¸öÁª½ÓÔËËãµÄ½á¹û£©

µ±ÄãÁª½ÓÁ½¸ö¹ØÏµÊ±£¬Áª½ÓËã·¨¶ÔÁ½¸ö¹ØÏµµÄ´¦ÀíÊDz»Í¬µÄ¡£ÔÚ±¾ÎÄÊ£Óಿ·Ö£¬ÎÒ½«¼Ù¶¨£º

Íâ¹ØÏµÊÇ×ó²àÊý¾Ý¼¯

ÄÚ¹ØÏµÊÇÓÒ²àÊý¾Ý¼¯

±ÈÈ磬 A JOIN B ÊÇ A ºÍ B µÄÁª½Ó£¬ÕâÀï A ÊÇÍâ¹ØÏµ£¬B ÊÇÄÚ¹ØÏµ¡£

¶àÊýÇé¿öÏ£¬ A JOIN B µÄ³É±¾¸ú B JOIN A µÄ³É±¾ÊDz»Í¬µÄ¡£

ÔÚÕâÒ»²¿·Ö£¬ÎÒ»¹½«¼Ù¶¨Íâ¹ØÏµÓÐ N ¸öÔªËØ£¬ÄÚ¹ØÏµÓÐ M ¸öÔªËØ¡£Òª¼Çס£¬ÕæÊµµÄÓÅ»¯Æ÷ͨ¹ýͳ¼ÆÖªµÀ N ºÍ M µÄÖµ¡£

×¢£ºN ºÍ M ÊǹØÏµµÄ»ùÊý¡£¡¾ÒëÕß×¢£º »ùÊý ¡¿

ǶÌ×Ñ­»·Áª½Ó

ǶÌ×Ñ­»·Áª½ÓÊÇ×î¼òµ¥µÄ¡£

µÀÀíÈçÏ£º

Õë¶ÔÍâ¹ØÏµµÄÿһÐÐ

²é¿´ÄÚ¹ØÏµÀïµÄËùÓÐÐÐÀ´Ñ°ÕÒÆ¥ÅäµÄÐÐ

ÏÂÃæÊÇα´úÂ룺

nested_loop_join(array outer, array inner)
for each row a in outer
for each row b in inner
if (match_join_condition(a,b))
write_result_in_output(a,b)
end if
end for
end for

ÓÉÓÚÕâÊǸöË«µü´ú£¬Ê±¼ä¸´ÔÓ¶ÈÊÇ O(N*M)¡£

ÔÚ´ÅÅÌ I/O ·½Ã棬 Õë¶Ô N ÐÐÍâ¹ØÏµµÄÿһÐУ¬ÄÚ²¿Ñ­»·ÐèÒª´ÓÄÚ¹ØÏµ¶ÁÈ¡ M ÐС£Õâ¸öËã·¨ÐèÒª´Ó´ÅÅ̶ÁÈ¡ N+ N*M ÐС£µ«ÊÇ£¬Èç¹ûÄÚ¹ØÏµ×㹻С£¬Äã¿ÉÒÔ°ÑËü¶ÁÈëÄڴ棬ÄÇô¾ÍֻʣÏ M + N ´Î¶ÁÈ¡¡£ÕâÑùÐÞ¸ÄÖ®ºó£¬ÄÚ¹ØÏµ±ØÐëÊÇ×îСµÄ£¬ÒòΪËüÓиü´ó»ú»á×°ÈëÄÚ´æ¡£

ÔÚCPU³É±¾·½ÃæÃ»ÓÐÊ²Ã´Çø±ð£¬µ«ÊÇÔÚ´ÅÅÌ I/O ·½Ã棬×îºÃ×îºÃµÄ£¬ÊÇÿ¸ö¹ØÏµÖ»¶Áȡһ´Î¡£

µ±È»£¬ÄÚ¹ØÏµ¿ÉÒÔÓÉË÷Òý´úÌæ£¬¶Ô´ÅÅÌ I/O ¸üÓÐÀû¡£

ÓÉÓÚÕâ¸öËã·¨·Ç³£¼òµ¥£¬ÏÂÃæÕâ¸ö°æ±¾ÔÚÄÚ¹ØÏµÌ«´óÎÞ·¨×°ÈëÄÚ´æÊ±£¬¶Ô´ÅÅÌ I/O ¸ü¼ÓÓÐÀû¡£µÀÀíÈçÏ£º

ΪÁ˱ÜÃâÖðÐжÁÈ¡Á½¸ö¹ØÏµ£¬

Äã¿ÉÒԳɴضÁÈ¡£¬°Ñ£¨Á½¸ö¹ØÏµÀï¶Áµ½µÄ£©Á½´ØÊý¾ÝÐб£´æÔÚÄÚ´æÀ

±È½ÏÁ½´ØÊý¾Ý£¬±£ÁôÆ¥ÅäµÄ£¬

È»ºó´Ó´ÅÅ̼ÓÔØÐµÄÊý¾Ý´ØÀ´¼ÌÐø±È½Ï

Ö±µ½¼ÓÔØÁËËùÓÐÊý¾Ý¡£

¿ÉÄܵÄËã·¨ÈçÏ£º

// improved version to reduce the disk I/O.
nested_loop_join_v2(file outer, file inner)
for each bunch ba in outer
// ba is now in memory
for each bunch bb in inner
// bb is now in memory
for each row a in ba
for each row b in bb
if (match_join_condition(a,b))
write_result_in_output(a,b)
end if
end for
end for
end for
end for

ʹÓÃÕâ¸ö°æ±¾£¬Ê±¼ä¸´ÔÓ¶ÈûÓб仯£¬µ«ÊÇ´ÅÅÌ·ÃÎʽµµÍÁË£º

ÓÃǰһ¸ö°æ±¾£¬Ëã·¨ÐèÒª N + N*M ´Î·ÃÎÊ£¨Ã¿´Î·ÃÎʶÁȡһÐУ©¡£

ÓÃа汾£¬´ÅÅÌ·ÃÎʱäΪ Íâ¹ØÏµµÄÊý¾Ý´ØÊýÁ¿ + Íâ¹ØÏµµÄÊý¾Ý´ØÊýÁ¿ * ÄÚ¹ØÏµµÄÊý¾Ý´ØÊýÁ¿¡£

Ôö¼ÓÊý¾Ý´ØµÄ³ß´ç£¬¿ÉÒÔ½µµÍ´ÅÅÌ·ÃÎÊ¡£

¹þÏ£Áª½Ó

¹þÏ£Áª½Ó¸ü¸´ÔÓ£¬²»¹ýÔںܶೡºÏ±ÈǶÌ×Ñ­»·Áª½Ó³É±¾µÍ¡£

¹þÏ£Áª½ÓµÄµÀÀíÊÇ£º

1) ¶ÁÈ¡ÄÚ¹ØÏµµÄËùÓÐÔªËØ

2) ÔÚÄÚ´æÀィһ¸ö¹þÏ£±í

3) ÖðÌõ¶ÁÈ¡Íâ¹ØÏµµÄËùÓÐÔªËØ

4) £¨ÓùþÏ£±íµÄ¹þÏ£º¯Êý£©¼ÆËãÿ¸öÔªËØµÄ¹þÏ£Öµ£¬À´²éÕÒÄÚ¹ØÏµÀïÏà¹ØµÄ¹þϣͰÄÚ

5) ÊÇ·ñÓëÍâ¹ØÏµµÄÔªËØÆ¥Åä¡£

ÔÚʱ¼ä¸´ÔÓ¶È·½ÃæÎÒÐèÒª×öЩ¼ÙÉèÀ´¼ò»¯ÎÊÌ⣺

ÄÚ¹ØÏµ±»»®·Ö³É X ¸ö¹þϣͰ

¹þÏ£º¯Êý¼¸ºõ¾ùÔȵطֲ¼Ã¿¸ö¹ØÏµÄÚÊý¾ÝµÄ¹þÏ£Öµ£¬¾ÍÊÇ˵¹þϣͰ´óСһÖ¡£

Íâ¹ØÏµµÄÔªËØÓë¹þϣͰÄÚµÄËùÓÐÔªËØµÄÆ¥Å䣬³É±¾ÊǹþϣͰÄÚÔªËØµÄÊýÁ¿¡£

ʱ¼ä¸´ÔÓ¶ÈÊÇ (M/X) * N + ´´½¨¹þÏ£±íµÄ³É±¾(M) + ¹þÏ£º¯ÊýµÄ³É±¾ * N ¡£

Èç¹û¹þÏ£º¯Êý´´½¨ÁË×㹻С¹æÄ£µÄ¹þϣͰ£¬ÄÇô¸´ÔӶȾÍÊÇ O(M+N)¡£

»¹Óиö¹þÏ£Áª½ÓµÄ°æ±¾£¬¶ÔÄÚ´æÓÐÀûµ«ÊǶԴÅÅÌ I/O ²»¹»ÓÐÀû¡£ Õâ»ØÊÇÕâÑùµÄ£º

1) ¼ÆËãÄÚ¹ØÏµºÍÍâ¹ØÏµË«·½µÄ¹þÏ£±í

2) ±£´æ¹þÏ£±íµ½´ÅÅÌ

3) È»ºóÖð¸ö¹þϣͰ±È½Ï£¨ÆäÖÐÒ»¸ö¶ÁÈëÄڴ棬ÁíÒ»¸öÖðÐжÁÈ¡£©¡£

ºÏ²¢Áª½Ó

ºÏ²¢Áª½ÓÊÇΨһ²úÉúÅÅÐòµÄÁª½ÓËã·¨¡£

×¢£ºÕâ¸ö¼ò»¯µÄºÏ²¢Áª½Ó²»Çø·ÖÄÚ±í»òÍâ±í£»Á½¸ö±í°çÑÝͬÑùµÄ½ÇÉ«¡£µ«ÊÇÕæÊµµÄʵÏÖ·½Ê½ÊDz»Í¬µÄ£¬±ÈÈçµ±´¦ÀíÖØ¸´ÖµÊ±¡£

1.£¨¿ÉÑ¡£©ÅÅÐòÁª½ÓÔËË㣺Á½¸öÊäÈëÔ´¶¼°´ÕÕÁª½Ó¹Ø¼ü×ÖÅÅÐò¡£

2.ºÏ²¢Áª½ÓÔËË㣺ÅÅÐòºóµÄÊäÈëÔ´ºÏ²¢µ½Ò»Æð¡£

ÅÅÐò

ÎÒÃÇÒѾ­Ì¸µ½¹ýºÏ²¢ÅÅÐò£¬ÔÚÕâÀïºÏ²¢ÅÅÐòÊǸöºÜºÃµÄËã·¨£¨µ«ÊDz¢·Ç×îºÃµÄ£¬Èç¹ûÄÚ´æ×ã¹»Óõϰ£¬»¹ÊǹþÏ£Áª½Ó¸üºÃ£©¡£

È»¶øÓÐʱÊý¾Ý¼¯ÒѾ­ÅÅÐòÁË£¬±ÈÈ磺

Èç¹û±íÄÚ²¿¾ÍÊÇÓÐÐòµÄ£¬±ÈÈçÁª½ÓÌõ¼þÀïÒ»¸öË÷Òý×éÖ¯±í ¡¾ÒëÕß×¢£º index-organized table ¡¿

Èç¹û¹ØÏµÊÇÁª½ÓÌõ¼þÀïµÄÒ»¸öË÷Òý

Èç¹ûÁª½ÓÓ¦ÓÃÔÚÒ»¸ö²éѯÖÐÒѾ­ÅÅÐòµÄÖмä½á¹û

ºÏ²¢Áª½Ó

Õⲿ·ÖÓëÎÒÃÇÑо¿¹ýµÄºÏ²¢ÅÅÐòÖеĺϲ¢ÔËËã·Ç³£ÏàËÆ¡£²»¹ýÕâÒ»´ÎÄØ£¬ÎÒÃDz»ÊÇ´ÓÁ½¸ö¹ØÏµÀïÌôÑ¡ËùÓÐÔªËØ£¬¶øÊÇÖ»ÌôÑ¡ÏàͬµÄÔªËØ¡£µÀÀíÈçÏ£º

1) ÔÚÁ½¸ö¹ØÏµÖУ¬±È½Ïµ±Ç°ÔªËØ£¨µ±Ç°=Í·Ò»´Î³öÏֵĵÚÒ»¸ö£©

2) Èç¹ûÏàͬ£¬¾Í°ÑÁ½¸öÔªËØ¶¼·ÅÈë½á¹û£¬ÔٱȽÏÁ½¸ö¹ØÏµÀïµÄÏÂÒ»¸öÔªËØ

3) Èç¹û²»Í¬£¬¾ÍÈ¥´øÓÐ×îÐ¡ÔªËØµÄ¹ØÏµÀïÕÒÏÂÒ»¸öÔªËØ£¨ÒòΪÏÂÒ»¸öÔªËØ¿ÉÄÜ»áÆ¥Å䣩

4) ÖØ¸´ 1¡¢2¡¢3²½ÖèÖ±µ½ÆäÖÐÒ»¸ö¹ØÏµµÄ×îºóÒ»¸öÔªËØ¡£

ÒòΪÁ½¸ö¹ØÏµ¶¼ÊÇÒÑÅÅÐòµÄ£¬Äã²»ÐèÒª¡º»ØÍ·È¥ÕÒ¡»£¬ËùÒÔÕâ¸ö·½·¨ÊÇÓÐЧµÄ¡£

¸ÃËã·¨ÊǸö¼ò»¯°æ£¬ÒòΪËüûÓд¦ÀíÁ½¸öÐòÁÐÖÐÏàͬÊý¾Ý³öÏÖ¶à´ÎµÄÇé¿ö£¨¼´¶àÖØÆ¥Å䣩¡£ÕæÊµ°æ±¾¡º½ö½ö¡»Õë¶Ô±¾Àý¾Í¸ü¼Ó¸´ÔÓ£¬ËùÒÔÎÒ²ÅÑ¡Ôñ¼ò»¯°æ¡£

Èç¹ûÁ½¸ö¹ØÏµ¶¼ÒѾ­ÅÅÐò£¬Ê±¼ä¸´ÔÓ¶ÈÊÇ O(N+M)

Èç¹ûÁ½¸ö¹ØÏµÐèÒªÅÅÐò£¬Ê±¼ä¸´ÔÓ¶ÈÊǶÔÁ½¸ö¹ØÏµÅÅÐòµÄ³É±¾£ºO(N*Log(N) + M*Log(M))

¶ÔÓÚ¼ÆËã»ú¼«¿Í£¬ÎÒ¸ø³öÏÂÃæÕâ¸ö¿ÉÄܵÄËã·¨À´´¦Àí¶àÖØÆ¥Å䣨ע£º¶ÔÓÚÕâ¸öËã·¨ÎÒ²»±£Ö¤100%ÕýÈ·£©£º

mergeJoin(relation a, relation b)
relation output
integer a_key:=0;
integer b_key:=0;

while (a[a_key]!=null and b[b_key]!=null)
if (a[a_key] < b[b_key])
a_key++;
else if (a[a_key] > b[b_key])
b_key++;
else //Join predicate satisfied
write_result_in_output(a[a_key],b[b_key])
//We need to be careful when we increase the pointers
if (a[a_key+1] != b[b_key])
b_key++;
end if
if (b[b_key+1] != a[a_key])
a_key++;
end if
if (b[b_key+1] == a[a_key] && b[b_key] == a[a_key+1])
b_key++;
a_key++;
end if
end if
end while

ÄĸöËã·¨×îºÃ£¿

Èç¹ûÓÐ×îºÃµÄ£¬¾Íû±ØÒªÅªÄÇô¶àÖÖÀàÐÍÁË¡£Õâ¸öÎÊÌâºÜÄÑ£¬ÒòΪºÜ¶àÒòËØ¶¼Òª¿¼ÂÇ£¬±ÈÈ磺

¿ÕÏÐÄڴ棺ûÓÐ×ã¹»µÄÄÚ´æµÄ»°¾Í¸úÇ¿´óµÄ¹þÏ£Áª½Ó°Ý°Ý°É£¨ÖÁÉÙÊÇÍêÈ«ÄÚ´æÖйþÏ£Áª½Ó£©¡£

Á½¸öÊý¾Ý¼¯µÄ´óС¡£±ÈÈ磬Èç¹ûÒ»¸ö´ó±íÁª½ÓÒ»¸öºÜСµÄ±í£¬ÄÇôǶÌ×Ñ­»·Áª½Ó¾Í±È¹þÏ£Áª½Ó¿ì£¬ÒòΪºóÕßÓд´½¨¹þÏ£µÄ¸ß°º³É±¾£»Èç¹ûÁ½¸ö±í¶¼·Ç³£´ó£¬ÄÇôǶÌ×Ñ­»·Áª½ÓCPU³É±¾¾ÍºÜ¸ß°º¡£

ÊÇ·ñÓÐË÷Òý£ºÓÐÁ½¸ö B+Ê÷Ë÷ÒýµÄ»°£¬´ÏÃ÷µÄÑ¡ÔñËÆºõÊǺϲ¢Áª½Ó¡£

½á¹ûÊÇ·ñÐèÒªÅÅÐò£º¼´Ê¹ÄãÓõ½µÄÊÇδÅÅÐòµÄÊý¾Ý¼¯£¬ÄãÒ²¿ÉÄÜÏëÓóɱ¾½Ï¸ßµÄºÏ²¢Áª½Ó£¨´øÅÅÐòµÄ£©£¬ÒòΪ×îÖյõ½ÅÅÐòµÄ½á¹ûºó£¬Äã¿ÉÒÔ°ÑËüºÍÁíÒ»¸öºÏ²¢Áª½Ó´®ÆðÀ´£¨»òÕßÒ²ÐíÒòΪ²éѯÓà ORDER BY/GROUP BY/DISTINCT µÈ²Ù×÷·ûÒþʽ»òÏÔʽµØÒªÇóÒ»¸öÅÅÐò½á¹û£©¡£

¹ØÏµÊÇ·ñÒѾ­ÅÅÐò£ºÕâʱºòºÏ²¢Áª½ÓÊÇ×îºÃµÄºòÑ¡Ïî¡£

Áª½ÓµÄÀàÐÍ£ºÊǵÈÖµÁª½Ó£¨±ÈÈç tableA.col1 = tableB.col2 £©£¿ »¹ÊÇÄÚÁª½Ó£¿ÍâÁª½Ó£¿µÑ¿¨¶û³Ë»ý£¿»òÕß×ÔÁª½Ó£¿ÓÐЩÁª½ÓÔÚÌØ¶¨»·¾³ÏÂÊÇÎÞ·¨¹¤×÷µÄ¡£

Êý¾ÝµÄ·Ö²¼£ºÈç¹ûÁª½ÓÌõ¼þµÄÊý¾ÝÊÇÇãбµÄ£¨±ÈÈç¸ù¾ÝÐÕÊÏÀ´Áª½ÓÈË£¬µ«ÊǺܶàÈËͬÐÕ£©£¬ÓùþÏ£Áª½Ó½«ÊǸöÔÖÄÑ£¬Ô­ÒòÊǹþÏ£º¯Êý½«²úÉú·Ö²¼¼«²»¾ùÔȵĹþϣͰ¡£

Èç¹ûÄãÏ£ÍûÁª½Ó²Ù×÷ʹÓöàÏ̻߳ò¶à½ø³Ì¡£

ÏëÒª¸üÏêϸµÄÐÅÏ¢£¬¿ÉÒÔÔĶÁDB2, ORACLE »ò SQL Server)µÄÎĵµ¡£

¼ò»¯µÄÀý×Ó

ÎÒÃÇÒѾ­Ñо¿ÁË 3 ÖÖÀàÐ͵ÄÁª½Ó²Ù×÷¡£

ÏÖÔÚ£¬±ÈÈç˵ÎÒÃÇÒªÁª½Ó 5 ¸ö±í£¬À´»ñµÃÒ»¸öÈ˵ÄÈ«²¿ÐÅÏ¢¡£Ò»¸öÈË¿ÉÒÔÓУº

¶à¸öÊÖ»úºÅ£¨MOBILES£©

¶à¸öÓÊÏ䣨MAILS£©

¶à¸öµØÖ·£¨ADRESSES£©

¶à¸öÒøÐÐÕ˺ţ¨BANK_ACCOUNTS£©

»»¾ä»°Ëµ£¬ÎÒÃÇÐèÒªÓÃÏÂÃæµÄ²éѯ¿ìËٵõ½´ð°¸£º

SELECT * from PERSON, MOBILES, MAILS,ADRESSES, BANK_ACCOUNTS
WHERE
PERSON.PERSON_ID = MOBILES.PERSON_ID
AND PERSON.PERSON_ID = MAILS.PERSON_ID
AND PERSON.PERSON_ID = ADRESSES.PERSON_ID
AND PERSON.PERSON_ID = BANK_ACCOUNTS.PERSON_ID

×÷Ϊһ¸ö²éѯÓÅ»¯Æ÷£¬ÎÒ±ØÐëÕÒµ½´¦ÀíÊý¾Ý×îºÃµÄ·½·¨¡£µ«ÓÐ 2 ¸öÎÊÌ⣺

ÿ¸öÁª½ÓʹÓÃÄÇÖÖÀàÐÍ£¿

ÎÒÓÐ 3 ÖÖ¿ÉÑ¡£¨¹þÏ£¡¢ºÏ²¢¡¢Ç¶Ì×£©£¬Í¬Ê±¿ÉÄÜÓõ½ 0, 1 »ò 2 ¸öË÷Òý£¨²»±ØËµ»¹ÓжàÖÖÀàÐ͵ÄË÷Òý£©¡£

°´Ê²Ã´Ë³ÐòÖ´ÐÐÁª½Ó£¿

±ÈÈ磬ÏÂͼÏÔʾÁËÕë¶Ô 4 ¸ö±í½ö½ö 3 ´ÎÁª½Ó£¬¿ÉÄܲÉÓõÄÖ´Ðмƻ®£º

ÄÇôÏÂÃæ¾ÍÊÇÎÒ¿ÉÄܲÉÈ¡µÄ·½·¨£º

1) ²ÉÈ¡´Ö±©µÄ·½Ê½

ÓÃÊý¾Ý¿âͳ¼Æ£¬¼ÆËãÿÖÖ¿ÉÄܵÄÖ´Ðмƻ®µÄ³É±¾£¬±£Áô×î¼Ñ·½°¸¡£µ«ÊÇ£¬»áÓкܶà¿ÉÄÜÐÔ¡£¶ÔÓÚÒ»¸ö¸ø¶¨Ë³ÐòµÄÁª½Ó²Ù×÷£¬Ã¿¸öÁª½ÓÓÐÈýÖÖ¿ÉÄÜÐÔ£º¹þÏ£¡¢ºÏ²¢¡¢Ç¶Ì×£¬ÄÇô×ܹ²¾ÍÓÐ 3^4 ÖÖ¿ÉÄÜÐÔ¡£È·¶¨Áª½ÓµÄ˳ÐòÊǸö¶þ²æÊ÷µÄÅÅÁÐÎÊÌ⣬»áÓÐ (2*4)!/(4+1)! ÖÖ¿ÉÄܵÄ˳Ðò¡£¶Ô±¾ÀýÕâ¸öÏ൱¼ò»¯Á˵ÄÎÊÌ⣬ÎÒ×îºó»áµÃµ½ 3^4*(2*4)!/(4+1)! ÖÖ¿ÉÄÜ¡£

Å׿ª×¨ÒµÊõÓÄÇÏ൱ÓÚ 27,216 ÖÖ¿ÉÄÜÐÔ¡£Èç¹û¸øºÏ²¢Áª½Ó¼ÓÉÏʹÓà 0,1 »ò 2 ¸ö B+Ê÷Ë÷Òý£¬¿ÉÄÜÐԾͱä³ÉÁË 210,000ÖÖ¡£ÎÒÊDz»ÊǸæËß¹ýÄãÕâ¸ö²éѯÆäʵ·Ç³£¼òµ¥Âð£¿

2) ÎÒ´ó½ÐÒ»Éù´ÇÁËÕâ·Ý¹¤×÷

ºÜÓÐÓÕ»óÁ¦£¬µ«ÊÇÕâÑùÒ»À´£¬Äã²»»áµÄµ½²éѯ½á¹û£¬¶øÎÒÐèҪǮÀ´¸¶Õ˵¥¡£

3) ÎÒÖ»³¢ÊÔ¼¸ÖÖÖ´Ðмƻ®£¬ÌôÒ»¸ö³É±¾×îµÍµÄ¡£

ÓÉÓÚ²»Êdz¬ÈË£¬ÎÒ²»ÄÜËã³öËùÓмƻ®µÄ³É±¾¡£Ïà·´£¬ÎÒ¿ÉÒÔÎä¶ÏµØ´ÓÈ«²¿¿ÉÄܵļƻ®ÖÐÑ¡ÔñÒ»¸ö×Ó¼¯£¬¼ÆËãËüÃǵijɱ¾£¬°Ñ×î¼ÑµÄ¼Æ»®¸øÄã¡£

4) ÎÒÓôÏÃ÷µÄ¹æÔòÀ´½µµÍ¿ÉÄÜÐÔµÄÊýÁ¿

ÓÐÁ½ÖÖ¹æÔò£º

ÎÒ¿ÉÒÔÓáºÂß¼­¡»¹æÔò£¬ËüÄÜÈ¥³ýÎÞÓõĿÉÄÜÐÔ£¬µ«ÊÇÎÞ·¨¹ýÂË´óÁ¿µÄ¿ÉÄÜÐÔ¡£±ÈÈ磺 ¡ºÇ¶Ì×Áª½ÓµÄÄÚ¹ØÏµ±ØÐëÊÇ×îСµÄÊý¾Ý¼¯¡»¡£

ÎÒ½ÓÊÜÏÖʵ£¬²»È¥ÕÒ×î¼Ñ·½°¸£¬Óøü¼¤½øµÄ¹æÔòÀ´´ó´ó½µµÍ¿ÉÄÜÐÔµÄÊýÁ¿¡£±ÈÈ磺¡ºÈç¹ûÒ»¸ö¹ØÏµºÜС£¬Ê¹ÓÃǶÌ×Ñ­»·Áª½Ó£¬¾ø²»Ê¹Óúϲ¢»ò¹þÏ£Áª½Ó¡£¡»

ÔÚÕâ¸ö¼òµ¥µÄÀý×ÓÖУ¬ÎÒ×îºóµÃµ½ºÜ¶à¿ÉÄÜÐÔ¡£µ«ÏÖʵÊÀ½çµÄ²éѯ»¹»áÓÐÆäËû¹ØÏµÔËËã·û£¬Ïñ OUTER JOIN, CROSS JOIN, GROUP BY, ORDER BY, PROJECTION, UNION, INTERSECT, DISTINCT ¡­ ÕâÒâζןü¶àµÄ¿ÉÄÜÐÔ¡£

ÄÇô£¬Êý¾Ý¿âÊÇÈçºÎ´¦ÀíµÄÄØ£¿

¶¯Ì¬¹æ»®£¬Ì°À·Ëã·¨ºÍÆô·¢Ê½Ëã·¨

¹ØÏµÐÍÊý¾Ý¿â»á³¢ÊÔÎÒ¸Õ¸ÕÌáµ½µÄ¶àÖÖ·½·¨£¬ÓÅ»¯Æ÷ÕæÕýµÄ¹¤×÷ÊÇÔÚÓÐÏÞʱ¼äÀïÕÒµ½Ò»¸öºÃµÄ½â¾ö·½°¸¡£

¶àÊýʱºò£¬ÓÅ»¯Æ÷ÕÒµ½µÄ²»ÊÇ×î¼ÑµÄ·½°¸£¬¶øÊÇÒ»¸ö¡º²»´í¡»µÄ

¶ÔÓÚС¹æÄ£µÄ²éѯ£¬²ÉÈ¡´Ö±©µÄ·½Ê½ÊÇÓпÉÄܵġ£µ«ÊÇΪÁËÈÃÖеȹæÄ£µÄ²éѯҲÄܲÉÈ¡´Ö±©µÄ·½Ê½£¬ÎÒÃÇÓа취±ÜÃâ²»±ØÒªµÄ¼ÆË㣬Õâ¾ÍÊǶ¯Ì¬¹æ»®¡£

¶¯Ì¬¹æ»®

Õ⼸¸ö×Ö±³ºóµÄÀíÄîÊÇ£¬ºÜ¶àÖ´Ðмƻ®ÊǷdz£ÏàËÆµÄ¡£¿´¿´ÏÂͼÕ⼸Öּƻ®£º

ËüÃǶ¼ÓÐÏàͬµÄ×ÓÊ÷£¨A JOIN B£©£¬ËùÒÔ£¬²»±ØÔÚÿ¸ö¼Æ»®ÖмÆËãÕâ¸ö×ÓÊ÷µÄ³É±¾£¬¼ÆËãÒ»´Î£¬±£´æ½á¹û£¬µ±ÔÙÓöµ½Õâ¸ö×ÓÊ÷Ê±ÖØÓá£ÓøüÕý¹æµÄ˵·¨£¬ÎÒÃÇÃæ¶ÔµÄÊǸöÖØµþÎÊÌ⡣ΪÁ˱ÜÃâ¶Ô²¿·Ö½á¹ûµÄÖØ¸´¼ÆË㣬ÎÒÃÇʹÓüÇÒä·¨¡£

Ó¦ÓÃÕâÒ»¼¼Êõ£¬ÎÒÃDz»ÔÙÓÐ (2*N)!/(N+1)! µÄ¸´ÔÓ¶È£¬¶øÊÇ¡°Ö»ÓС± 3^N¡£ÔÚ֮ǰ 4 ¸öJOIN µÄÀý×ÓÀÕâÒâζ׎« 336 ´ÎÅÅÐò½µÎª 81 ´Î¡£Èç¹ûÊÇ´óһЩµÄ²éѯ£¬±ÈÈç 8 ¸ö JOIN £¨ÆäʵҲ²»ÊǺܴóÀ²£©£¬¾ÍÊǽ« 57,657,600 ´Î½µÎª 6551 ´Î¡£¡¾ÒëÕß×¢£ºÕâһС¶Î©µôÁË£¬¸Ðл nsosÖ¸³öÀ´¡£ÁíÍâ¸Ðл Clark Li Ö¸³öDynamic Programing Ó¦¸Ã·­ÒëΪ¶¯Ì¬¹æ»®¡£ ¡¿

¶ÔÓÚ¼ÆËã»ú¼«¿Í£¬ÏÂÃæÊÇÎÒÔÚÏÈǰ¸øÄãµÄ½Ì³ÌÀïÕÒµ½µÄÒ»¸öËã·¨¡£ÎÒ²»Ìṩ½âÊÍ£¬ËùÒÔ½öÔÚÄãÒѾ­Á˽⶯̬¹æ»®»òÕß¾«Í¨Ëã·¨µÄÇé¿öÏÂÔĶÁ£¨ÎÒÌáÐѹýÄãŶ£©£º

procedure findbestplan(S)
if (bestplan[S].cost infinite)
return bestplan[S]
// else bestplan[S] has not been computed earlier, compute it now
if (S contains only 1 relation)
set bestplan[S].plan and bestplan[S].cost based on the best way
of accessing S /* Using selections on S and indices on S */
else for each non-empty subset S1 of S such that S1 != S
P1= findbestplan(S1)
P2= findbestplan(S - S1)
A = best algorithm for joining results of P1 and P2
cost = P1.cost + P2.cost + cost of A
if cost < bestplan[S].cost
bestplan[S].cost = cost
bestplan[S].plan = ¡ºexecute P1.plan; execute P2.plan;
join results of P1 and P2 using A¡»
return bestplan[S]

Õë¶Ô´ó¹æÄ£²éѯ£¬ÄãÒ²¿ÉÒÔÓö¯Ì¬¹æ»®·½·¨£¬µ«ÊÇÒª¸½¼Ó¶îÍâµÄ¹æÔò£¨»òÕß³ÆÎªÆô·¢Ê½Ëã·¨£©À´¼õÉÙ¿ÉÄÜÐÔ¡£

Èç¹ûÎÒÃǽö·ÖÎöÒ»¸öÌØ¶¨ÀàÐ͵ļƻ®£¨ÀýÈç×óÉîÊ÷ left-deep tree£¬²Î¿¼)£¬ÎÒÃǵõ½ n*2^n ¶ø²»ÊÇ 3^n¡£

Èç¹ûÎÒÃǼÓÉÏÂß¼­¹æÔòÀ´±ÜÃâһЩģʽµÄ¼Æ»®£¨Ïñ¡ºÈç¹ûÒ»¸ö±íÓÐÕë¶ÔÖ¸¶¨Î½´ÊµÄË÷Òý£¬¾Í²»Òª¶Ô±í³¢ÊԺϲ¢Áª½Ó£¬Òª¶ÔË÷Òý¡»£©£¬¾Í»áÔÚ²»¸ø×î¼Ñ·½°¸Ôì³É¹ý¶àÉ˺¦µÄǰÌáÏ£¬¼õÉÙ¿ÉÄÜÐÔµÄÊýÁ¿¡£¡¾ÒëÕß×¢£ºÔ­ÎÄÓ¦¸ÃÊÇÓÐÁ½´¦±ÊÎó£º as=has, to=too¡¿

Èç¹ûÎÒÃÇÔÚÁ÷³ÌÀïÔö¼Ó¹æÔò£¨Ïñ¡ºÁª½ÓÔËËãÏÈÓÚÆäËûËùÓеĹØÏµÔËËã¡»£©£¬Ò²ÄܼõÉÙ´óÁ¿µÄ¿ÉÄÜÐÔ¡£

¡­¡­

̰À·Ëã·¨

µ«ÊÇ£¬ÓÅ»¯Æ÷Ãæ¶ÔÒ»¸ö·Ç³£´óµÄ²éѯ£¬»òÕßΪÁ˾¡¿ìÕÒµ½´ð°¸£¨È»¶ø²éѯËٶȾͿ첻ÆðÀ´ÁË£©£¬»áÓ¦ÓÃÁíÒ»ÖÖËã·¨£¬½Ð̰À·Ëã·¨¡£

Ô­ÀíÊǰ´ÕÕÒ»¸ö¹æÔò£¨»òÆô·¢£©ÒÔ½¥½øµÄ·½Ê½Öƶ¨²éѯ¼Æ»®¡£ÔÚÕâ¸ö¹æÔòÏ£¬Ì°À·Ëã·¨Öð²½Ñ°ÕÒ×î¼ÑËã·¨£¬ÏÈ´¦ÀíÒ»ÌõJOIN£¬½Ó×Åÿһ²½°´ÕÕͬÑù¹æÔò¼ÓÒ»ÌõеÄJOIN¡£

ÎÒÃÇÀ´¿´¸ö¼òµ¥µÄÀý×Ó¡£±ÈÈçÒ»¸öÕë¶Ô5ÕÅ±í£¨A,B,C,D,E£©4´ÎJOIN µÄ²éѯ£¬ÎªÁ˼ò»¯ÎÒÃǰÑǶÌ×JOIN×÷Ϊ¿ÉÄܵÄÁª½Ó·½Ê½£¬°´ÕÕ¡ºÊ¹ÓÃ×îµÍ³É±¾µÄÁª½Ó¡»¹æÔò¡£

Ö±½Ó´Ó 5 ¸ö±íÀïѡһ¸ö¿ªÊ¼£¨±ÈÈç A£©

¼ÆËãÿһ¸öÓë A µÄÁª½Ó£¨A ×÷ΪÄÚ¹ØÏµ»òÍâ¹ØÏµ£©

·¢ÏÖ ¡°A JOIN B¡± ³É±¾×îµÍ

¼ÆËãÿһ¸öÓë ¡°A JOIN B¡± µÄ½á¹ûÁª½ÓµÄ³É±¾£¨¡°A JOIN B¡± ×÷ΪÄÚ¹ØÏµ»òÍâ¹ØÏµ£©

·¢ÏÖ ¡°(A JOIN B) JOIN C¡± ³É±¾×îµÍ

¼ÆËãÿһ¸öÓë ¡°(A JOIN B) JOIN C¡± µÄ½á¹ûÁª½ÓµÄ³É±¾ ¡­¡­

×îºóÈ·¶¨Ö´Ðмƻ® ¡°( ( (A JOIN B) JOIN C) JOIN D ) JOIN E )¡±

ÒòΪÎÒÃÇÊÇÎä¶ÏµØ´Ó±í A ¿ªÊ¼£¬ÎÒÃÇ¿ÉÒÔ°ÑͬÑùµÄËã·¨ÓÃÔÚ B£¬È»ºó C£¬È»ºó D, È»ºó E¡£×îºó±£Áô³É±¾×îµÍµÄÖ´Ðмƻ®¡£

˳±ã˵һ¾ä£¬Õâ¸öËã·¨ÓиöÃû×Ö£¬½Ð¡º×î½üÁÚ¾ÓËã·¨¡»¡£

Å׿ªÏ¸½Ú²»Ì¸£¬Ö»ÐèÒ»¸öÁ¼ºÃµÄÄ£ÐͺÍÒ»¸ö N*log(N) ¸´ÔӶȵÄÅÅÐò£¬ÎÊÌâ¾ÍÇáËɽâ¾öÁË¡£Õâ¸öËã·¨µÄ¸´ÔÓ¶ÈÊÇ O(N*log(N)) £¬¶Ô±ÈÒ»ÏÂÍêÈ«¶¯Ì¬¹æ»®µÄ O(3^N)¡£Èç¹ûÄãÓиö20¸öÁª½ÓµÄ´óÐͲéѯ£¬ÕâÒâζ×Å 26 vs 3,486,784,401 £¬ÌìÈÀÖ®±ð£¡

Õâ¸öËã·¨µÄÎÊÌâÊÇ£¬ÎÒÃÇ×öµÄ¼ÙÉèÊÇ£ºÕÒµ½ 2 ¸ö±íµÄ×î¼ÑÁª½Ó·½·¨£¬±£ÁôÕâ¸öÁª½Ó½á¹û£¬ÔÙÁª½ÓÏÂÒ»¸ö±í£¬¾ÍÄܵõ½×îµÍµÄ³É±¾¡£µ«ÊÇ£º

¼´Ê¹ÔÚ A, B, C Ö®¼ä£¬A JOIN B ¿ÉµÃ×îµÍ³É±¾

(A JOIN C) JOIN B Ò²Ðí±È (A JOIN B) JOIN C ¸üºÃ¡£

ΪÁ˸ÄÉÆÕâÒ»×´¿ö£¬Äã¿ÉÒÔ¶à´ÎʹÓûùÓÚ²»Í¬¹æÔòµÄ̰À·Ëã·¨£¬²¢±£Áô×î¼ÑµÄÖ´Ðмƻ®¡£

ÆäËûËã·¨

[ Èç¹ûÄãÒѾ­Êܹ»ÁËËã·¨»°Ì⣬¾ÍÖ±½ÓÌøµ½ÏÂÒ»²¿·Ö¡£Õⲿ·Ö¶ÔÎÄÕÂÓàϵÄÄÚÈݲ»ÖØÒª¡£] ¡¾ÒëÕß×¢£ºÎÒÒ²ºÜÏë°ÑÕâ¶ÎÌø¹ýÈ¥ -_- ¡¿

ºÜ¶à¼ÆËã»ú¿ÆÑ§Ñо¿ÕßÈÈÖÔÓÚѰÕÒ×î¼ÑµÄÖ´Ðмƻ®£¬ËûÃǾ­³£ÎªÌض¨ÎÊÌâ»òģʽ̽Ѱ¸üºÃµÄ½â¾ö·½°¸£¬±ÈÈ磺

Èç¹û²éѯÊÇÐÇÐÍÁª½Ó£¨Ò»ÖÖ¶àÁª½Ó²éѯ£©£¬Ä³Ð©Êý¾Ý¿âʹÓÃÒ»ÖÖÌØ¶¨µÄËã·¨¡£

Èç¹û²éѯÊDz¢Ðеģ¬Ä³Ð©Êý¾Ý¿âʹÓÃÒ»ÖÖÌØ¶¨µÄËã·¨¡£ ¡­¡­

ÆäËûËã·¨Ò²ÔÚÑо¿Ö®ÖУ¬¾ÍÊÇΪÁËÌæ»»ÔÚ´óÐͲéѯÖеĶ¯Ì¬¹æ»®Ëã·¨¡£Ì°À·Ëã·¨ÊôÓÚÒ»¸ö½Ð×öÆô·¢Ê½Ëã·¨µÄ´ó¼Ò×壬Ëü¸ù¾ÝÒ»Ìõ¹æÔò£¨»òÆô·¢£©£¬±£´æÉÏÒ»²½ÕÒµ½µÄ·½·¨£¬¡º¸½¼Ó¡»µ½µ±Ç°²½ÖèÀ´½øÒ»²½ËÑѰ½â¾ö·½·¨¡£ÓÐЩËã·¨¸ù¾ÝÌØ¶¨¹æÔò£¬Ò»²½²½µÄÓ¦ÓùæÔòµ«²»×ÜÊDZ£ÁôÉÏÒ»²½ÕÒµ½µÄ×î¼Ñ·½·¨¡£ËüÃÇͳ³ÆÆô·¢Ê½Ëã·¨¡£

±ÈÈ磬»ùÒòËã·¨¾ÍÊÇÒ»ÖÖ£º

Ò»¸ö·½·¨´ú±íÒ»ÖÖ¿ÉÄܵÄÍêÕû²éѯ¼Æ»®

ÿһ²½±£ÁôÁË P ¸ö·½·¨£¨¼´¼Æ»®£©£¬¶ø²»ÊÇÒ»¸ö¡£

0) P ¸ö¼Æ»®Ëæ»ú´´½¨

1) ³É±¾×îµÍµÄ¼Æ»®²Å»á±£Áô

2) ÕâЩ×î¼Ñ¼Æ»®»ìºÏÔÚÒ»Æð²úÉú P ¸öеļƻ®

3) һЩеļƻ®±»Ëæ»ú¸Äд

4) 1£¬2£¬3²½Öظ´ T ´Î

5) È»ºóÔÚ×îºóÒ»´ÎÑ­»·£¬´Ó P ¸ö¼Æ»®ÀïµÃµ½×î¼Ñ¼Æ»®¡£

Ñ­»·´ÎÊýÔ½¶à£¬¼Æ»®¾ÍÔ½ºÃ¡£

ÕâÊÇħÊõ£¿²»£¬ÕâÊÇ×ÔÈ»·¨Ôò£ºÊÊÕßÉú´æ£¡

PostgreSQL ʵÏÖÁË»ùÒòËã·¨£¬µ«ÎÒ²¢Ã»Óз¢ÏÖËüÊDz»ÊÇĬÈÏʹÓÃÕâÖÖËã·¨µÄ¡£

Êý¾Ý¿âÖл¹Ê¹ÓÃÁËÆäËüÆô·¢Ê½Ëã·¨£¬Ïñ¡ºÄ£ÄâÍË»ðËã·¨£¨Simulated Annealing£©¡»¡¢¡º½»»¥Ê½¸ÄÁ¼Ëã·¨£¨Iterative Improvement£©¡»¡¢¡ºË«½×¶ÎÓÅ»¯Ëã·¨£¨Two-Phase Optimization£©¡»¡­..²»¹ý£¬ÎÒ²»ÖªµÀÕâЩËã·¨µ±Ç°ÊÇ·ñÔÚÆóÒµ¼¶Êý¾Ý¿âÓ¦ÓÃÁË£¬»¹Êǽö½öÓÃÔÚÑо¿ÐÍÊý¾Ý¿â¡£

Èç¹ûÏë½øÒ»²½Á˽⣬ÕâÆªÑо¿ÎÄÕ½éÉÜÁ½¸ö¸ü¶à¿ÉÄܵÄËã·¨¡¶Êý¾Ý¿â²éѯÓÅ»¯ÖÐÁª½ÓÅÅÐòÎÊÌâµÄËã·¨×ÛÊö¡·£¬Äã¿ÉÒÔÈ¥ÔĶÁһϡ£

ÕæÊµµÄÓÅ»¯Æ÷

[ Õâ¶Î²»ÖØÒª£¬¿ÉÒÔÌø¹ý ]

È»¶ø£¬ËùÓÐÉÏÊöÂÞÀïÂÞàµĶ¼·Ç³£ÀíÂÛ»¯£¬ÎÒÊǸö¿ª·¢Õß¶ø²»ÊÇÑо¿Õߣ¬ÎÒϲ»¶¾ßÌåµÄÀý×Ó¡£

ÎÒÃÇÀ´¿´¿´ SQLite ÓÅ»¯Æ÷ ÊÇÔõô¹¤×÷µÄ¡£ÕâÊǸöÇáÁ¿»¯Êý¾Ý¿â£¬ËüʹÓÃÒ»ÖÖ¼òµ¥ÓÅ»¯Æ÷£¬»ùÓÚ´øÓи½¼Ó¹æÔòµÄ̰À·Ëã·¨£¬À´ÏÞÖÆ¿ÉÄÜÐÔµÄÊýÁ¿¡£

SQLite ÔÚÓÐ CROSS JOIN ²Ù×÷·ûʱ´Ó²»¸ø±íÖØÐÂÅÅÐò

ʹÓÃǶÌ×Áª½Ó

ÍâÁª½ÓʼÖÕ°´Ë³ÐòÆÀ¹À

¡­¡­

3.8.0֮ǰµÄ°æ±¾Ê¹Óáº×î½üÁÚ¾Ó¡»Ì°À·Ëã·¨À´ËÑѰ×î¼Ñ²éѯ¼Æ»®

µÈµÈ¡­¡­ÎÒÃǼû¹ýÕâ¸öËã·¨£¡ÕæÊÇÇɹþ£¡

´Ó3.8.0°æ±¾£¨·¢²¼ÓÚ2015Ä꣩¿ªÊ¼£¬SQLiteʹÓáºN×î½üÁÚ¾Ó¡»Ì°À·Ëã·¨À´ËÑѰ×î¼Ñ²éѯ¼Æ»®

ÎÒÃÇÔÙ¿´¿´ÁíÒ»¸öÓÅ»¯Æ÷ÊÇÔõô¹¤×÷µÄ¡£IBM DB2 ¸úËùÓÐÆóÒµ¼¶Êý¾Ý¿â¶¼ÀàËÆ£¬ÎÒÌÖÂÛËüÊÇÒòΪÔÚÇл»µ½´óÊý¾Ý֮ǰ£¬ËüÊÇÎÒ×îºóÕæÕýʹÓõÄÊý¾Ý¿â¡£

¿´¹ý¹Ù·½Îĵµºó£¬ÎÒÃÇÁ˽⵽ DB2 ÓÅ»¯Æ÷¿ÉÒÔÈÃÄãʹÓà 7 ÖÖ¼¶±ðµÄÓÅ»¯£º

¶ÔÁª½ÓʹÓÃ̰À·Ëã·¨

0 ¨C ×îСÓÅ»¯£¬Ê¹ÓÃË÷ÒýɨÃèºÍǶÌ×Ñ­»·Áª½Ó£¬±ÜÃâһЩ²éÑ¯ÖØÐ´

1 ¨C µÍ¼¶ÓÅ»¯

2 ¨C ÍêÈ«ÓÅ»¯

¶ÔÁª½ÓʹÓö¯Ì¬¹æ»®Ëã·¨

3 ¨C ÖеÈÓÅ»¯ºÍ´ÖÂԵĽüËÆ·¨

5 ¨C ÍêÈ«ÓÅ»¯£¬Ê¹ÓôøÓÐÆô·¢Ê½µÄËùÓм¼Êõ

7 ¨C ÍêÈ«ÓÅ»¯£¬ÀàËÆ¼¶±ð5£¬µ«²»ÓÃÆô·¢Ê½

9 ¨C ×î´óÓÅ»¯£¬ÍêÈ«²»¹Ë¿ªÏú£¬¿¼ÂÇËùÓпÉÄܵÄÁª½Ó˳Ðò£¬°üÀ¨µÑ¿¨¶û³Ë»ý

¿ÉÒÔ¿´µ½ DB2 ʹÓÃ̰À·Ëã·¨ºÍ¶¯Ì¬¹æ»®Ëã·¨¡£µ±È»£¬ËûÃDz»»á°Ñ×Ô¼ºµÄÆô·¢Ëã·¨·ÖÏí³öÀ´µÄ£¬ÒòΪ²éѯÓÅ»¯Æ÷ÊÇÊý¾Ý¿âµÄ¿´¼Ò±¾Áì¡£

DB2 µÄĬÈϼ¶±ðÊÇ 5£¬ÓÅ»¯Æ÷ʹÓÃÏÂÁÐÌØÐÔ£º ¡¾ÒëÕß×¢£ºÒÔϳöÏÖµÄһЩ¸ÅÄîÎÒûÓÐ×ö¿¼Ö¤£¬ÒòΪ[ Õâ¶Î²»ÖØÒª£¬¿ÉÒÔÌø¹ý ]¡¿

ʹÓÃËùÓпÉÓõÄͳ¼Æ£¬°üÀ¨Ïß¶ÎÊ÷£¨frequent-value£©ºÍ·ÖλÊýͳ¼Æ£¨quantile statistics£©¡£

ʹÓÃËùÓвéÑ¯ÖØÐ´¹æÔò£¨º¬Îﻯ²éѯ±í·ÓÉ£¬materialized query table routing£©£¬³ýÁËÔÚ¼«ÉÙÇé¿öÏÂÊÊÓõļÆËãÃܼ¯Ð͹æÔò¡£

ʹÓö¯Ì¬¹æ»®Ä£ÄâÁª½Ó

ÓÐÏÞʹÓÃ×éºÏÄÚ¹ØÏµ£¨composite inner relation£©

¶ÔÓÚÉæ¼°²éÕÒ±íµÄÐÇÐÍģʽ£¬ÓÐÏÞʹÓõѿ¨¶û³Ë»ý

¿¼ÂÇ¿í·ºµÄ·ÃÎÊ·½Ê½£¬º¬ÁбíԤȡ£¨list prefetch£¬×¢£ºÎÒÃǽ«ÌÖÂÛʲôÊÇÁбíԤȡ£©£¬index ANDing£¨×¢£ºÒ»ÖÖ¶ÔË÷ÒýµÄÌØÊâ²Ù×÷£©£¬ºÍÎﻯ²éѯ±í·ÓÉ¡£

ĬÈϵģ¬DB2 ¶ÔÁª½ÓÅÅÁÐʹÓÃÊÜÆô·¢Ê½ÏÞÖÆµÄ¶¯Ì¬¹æ»®Ëã·¨¡£

ÆäËüÇé¿ö (GROUP BY, DISTINCT¡­) Óɼòµ¥¹æÔò´¦Àí¡£

²éѯ¼Æ»®»º´æ

ÓÉÓÚ´´½¨²éѯ¼Æ»®ÊǺÄʱµÄ£¬´ó¶àÊý¾Ý¿â°Ñ¼Æ»®±£´æÔÚ²éѯ¼Æ»®»º´æ£¬À´±ÜÃâÖØ¸´¼ÆËã¡£Õâ¸ö»°Ìâ±È½Ï´ó£¬ÒòΪÊý¾Ý¿âÐèÒªÖªµÀʲôʱºò¸üйýʱµÄ¼Æ»®¡£°ì·¨ÊÇÉèÖÃÒ»¸öÉÏÏÞ£¬Èç¹ûÒ»¸ö±íµÄͳ¼Æ±ä»¯³¬¹ýÁËÉÏÏÞ£¬¹ØÓڸñíµÄ²éѯ¼Æ»®¾Í´Ó»º´æÖÐÇå³ý¡£

²éѯִÐÐÆ÷

ÔÚÕâ¸ö½×¶Î£¬ÎÒÃÇÓÐÁËÒ»¸öÓÅ»¯µÄÖ´Ðмƻ®£¬ÔÙ±àÒëΪ¿ÉÖ´ÐдúÂ롣Ȼºó£¬Èç¹ûÓÐ×ã¹»×ÊÔ´£¨Äڴ棬CPU£©£¬²éѯִÐÐÆ÷¾Í»áÖ´ÐÐËü¡£¼Æ»®ÖеIJÙ×÷·û (JOIN, SORT BY ¡­) ¿ÉÒÔ˳Ðò»ò²¢ÐÐÖ´ÐУ¬ÕâÈ¡¾öÓÚÖ´ÐÐÆ÷¡£ÎªÁË»ñµÃºÍдÈëÊý¾Ý£¬²éѯִÐÐÆ÷ÓëÊý¾Ý¹ÜÀíÆ÷½»»¥£¬±¾ÎÄÏÂÒ»²¿·ÖÀ´ÌÖÂÛÊý¾Ý¹ÜÀíÆ÷¡£

Êý¾Ý¹ÜÀíÆ÷

ÔÚÕâÒ»²½£¬²éѯ¹ÜÀíÆ÷Ö´ÐÐÁ˲éѯ£¬ÐèÒª´Ó±íºÍË÷Òý»ñÈ¡Êý¾Ý£¬ÓÚÊÇÏòÊý¾Ý¹ÜÀíÆ÷Ìá³öÇëÇó¡£µ«ÊÇÓÐ 2 ¸öÎÊÌ⣺

¹ØÏµÐÍÊý¾Ý¿âʹÓÃÊÂÎñÄ£ÐÍ£¬ËùÒÔ£¬µ±ÆäËûÈËÔÚͬһʱ¿ÌʹÓûòÐÞ¸ÄÊý¾Ýʱ£¬ÄãÎÞ·¨µÃµ½Õⲿ·ÖÊý¾Ý¡£

Êý¾ÝÌáÈ¡ÊÇÊý¾Ý¿âÖÐËÙ¶È×îÂýµÄ²Ù×÷£¬ËùÒÔÊý¾Ý¹ÜÀíÆ÷ÐèÒª×ã¹»´ÏÃ÷µØ»ñµÃÊý¾Ý²¢±£´æÔÚÄڴ滺³åÇøÄÚ¡£

ÔÚÕâÒ»²¿·Ö£¬ÎÒû¿´¿´¹ØÏµÐÍÊý¾Ý¿âÊÇÈçºÎ´¦ÀíÕâÁ½¸öÎÊÌâµÄ¡£ÎÒ²»»á½²Êý¾Ý¹ÜÀíÆ÷ÊÇÔõô»ñµÃÊý¾ÝµÄ£¬ÒòΪÕâ²»ÊÇ×îÖØÒªµÄ£¨¶øÇÒ±¾ÎÄÒѾ­¹»³¤µÄÁË£¡£©¡£

»º´æ¹ÜÀíÆ÷

ÎÒÒѾ­Ëµ¹ý£¬Êý¾Ý¿âµÄÖ÷Ҫƿ¾±ÊÇ´ÅÅÌ I/O¡£ÎªÁËÌá¸ßÐÔÄÜ£¬ÏÖ´úÊý¾Ý¿âʹÓûº´æ¹ÜÀíÆ÷¡£

²éѯִÐÐÆ÷²»»áÖ±½Ó´ÓÎļþϵͳÄÃÊý¾Ý£¬¶øÊÇÏò»º´æ¹ÜÀíÆ÷Òª¡£»º´æ¹ÜÀíÆ÷ÓÐÒ»¸öÄڴ滺´æÇø£¬½Ð×ö»º³å³Ø£¬´ÓÄÚ´æ¶ÁÈ¡Êý¾ÝÏÔÖøµØÌáÉýÊý¾Ý¿âÐÔÄÜ¡£¶Ô´ËºÜÄѸø³öÒ»¸öÊýÁ¿¼¶£¬ÒòΪÕâÈ¡¾öÓÚÄãÐèÒªµÄÊÇÄÄÖÖ²Ù×÷£º

˳Ðò·ÃÎÊ£¨±ÈÈ磺ȫɨÃ裩 vs Ëæ»ú·ÃÎÊ£¨±ÈÈ磺°´ÕÕrow id·ÃÎÊ£©

¶Á»¹ÊÇд

ÒÔ¼°Êý¾Ý¿âʹÓõĴÅÅÌÀàÐÍ£º

7.2k/10k/15k rpmµÄÓ²ÅÌ

SSD

RAID 1/5/¡­

ÒªÎÒ˵£¬ÄÚ´æ±È´ÅÅÌÒª¿ì100µ½10Íò±¶¡£

È»¶ø£¬Õâµ¼ÖÂÁËÁíÒ»¸öÎÊÌ⣨Êý¾Ý¿â×ÜÊÇÕâÑù¡­)£¬»º´æ¹ÜÀíÆ÷ÐèÒªÔÚ²éѯִÐÐÆ÷ʹÓÃÊý¾Ý֮ǰµÃµ½Êý¾Ý£¬·ñÔò²éѯ¹ÜÀíÆ÷²»µÃ²»µÈ´ýÊý¾Ý´Ó»ºÂýµÄ´ÅÅÌÖжÁ³öÀ´¡£

Ô¤¶Á

Õâ¸öÎÊÌâ½ÐÔ¤¶Á¡£²éѯִÐÐÆ÷ÖªµÀËü½«ÐèҪʲôÊý¾Ý£¬ÒòΪËüÁ˽âÕû¸ö²éѯÁ÷£¬¶øÇÒͨ¹ýͳ¼ÆÒ²Á˽â´ÅÅÌÉϵÄÊý¾Ý¡£µÀÀíÊÇÕâÑùµÄ£º

µ±²éѯִÐÐÆ÷´¦ÀíËüµÄµÚÒ»ÅúÊý¾Ýʱ

»á¸æËß»º´æ¹ÜÀíÆ÷Ô¤ÏÈ×°ÔØµÚ¶þÅúÊý¾Ý

µ±¿ªÊ¼´¦ÀíµÚ¶þÅúÊý¾Ýʱ

¸æËß»º´æ¹ÜÀíÆ÷Ô¤ÏÈ×°ÔØµÚÈýÅúÊý¾Ý£¬²¢ÇÒ¸æËß»º´æ¹ÜÀíÆ÷µÚÒ»Åú¿ÉÒÔ´Ó»º´æÀïÇåµôÁË¡£

¡­¡­

»º´æ¹ÜÀíÆ÷ÔÚ»º³å³ØÀï±£´æËùÓеÄÕâЩÊý¾Ý¡£ÎªÁËÈ·¶¨Ò»ÌõÊý¾ÝÊÇ·ñÓÐÓ㬻º´æ¹ÜÀíÆ÷¸ø»º´æµÄÊý¾ÝÌí¼ÓÁ˶îÍâµÄÐÅÏ¢£¨½ÐãÅËø£©¡£

ÓÐʱ²éѯִÐÐÆ÷²»ÖªµÀËüÐèҪʲôÊý¾Ý£¬ÓеÄÊý¾Ý¿âÒ²²»ÌṩÕâ¸ö¹¦ÄÜ¡£Ïà·´£¬ËüÃÇʹÓÃÒ»ÖÖÍÆ²âÔ¤¶Á·¨£¨±ÈÈ磺Èç¹û²éѯִÐÐÆ÷ÏëÒªÊý¾Ý1¡¢3¡¢5£¬Ëü²»¾ÃºóºÜ¿ÉÄÜ»áÒª 7¡¢9¡¢11£©£¬»òÕß˳ÐòÔ¤¶Á·¨£¨Õâʱºò»º´æ¹ÜÀíÆ÷Ö»ÊǶÁȡһÅúÊý¾Ýºó¼òµ¥µØ´Ó´ÅÅ̼ÓÔØÏÂÒ»ÅúÁ¬ÐøÊý¾Ý£©¡£

ΪÁË¼à¿ØÔ¤¶ÁµÄ¹¤×÷×´¿ö£¬ÏÖ´úÊý¾Ý¿âÒýÈëÁËÒ»¸ö¶ÈÁ¿½Ð»º³å/»º´æÃüÖÐÂÊ£¬ÓÃÀ´ÏÔʾÇëÇóµÄÊý¾ÝÔÚ»º´æÖÐÕÒµ½¶ø²»ÊÇ´Ó´ÅÅ̶ÁÈ¡µÄƵÂÊ¡£

×¢£ºÔã¸âµÄ»º´æÃüÖÐÂʲ»×ÜÊÇÒâζ×Å»º´æ¹¤×÷״̬²»¼Ñ¡£¸ü¶àÐÅÏ¢ÇëÔĶÁOracleÎĵµ¡£

»º³åÖ»ÊÇÈÝÁ¿ÓÐÏÞµÄÄÚ´æ¿Õ¼ä£¬Òò´Ë£¬ÎªÁ˼ÓÔØÐµÄÊý¾Ý£¬ËüÐèÒªÒÆ³ýһЩÊý¾Ý¡£¼ÓÔØºÍÇå³ý»º´æÐèҪһЩ´ÅÅ̺ÍÍøÂçI/OµÄ³É±¾¡£Èç¹ûÄãÓиö¾­³£Ö´ÐеIJéѯ£¬ÄÇôÿ´Î¶¼°Ñ²éѯ½á¹û¼ÓÔØÈ»ºóÇå³ý£¬Ð§ÂʾÍÌ«µÍÁË¡£ÏÖ´úÊý¾Ý¿âÓûº³åÇøÖû»²ßÂÔÀ´½â¾öÕâ¸öÎÊÌâ¡£

»º³åÇøÖû»²ßÂÔ

¶àÊýÏÖ´úÊý¾Ý¿â(ÖÁÉÙ SQL Server, MySQL, Oracle ºÍ DB2)ʹÓà LRU Ëã·¨¡£

LRU

LRU´ú±í×î½ü×îÉÙʹÓã¨Least Recently Used£©Ëã·¨£¬±³ºóµÄÔ­ÀíÊÇ£ºÔÚ»º´æÀï±£ÁôµÄÊý¾ÝÊÇ×î½üʹÓõģ¬ËùÒÔ¸üÓпÉÄÜÔÙ´ÎʹÓá£

ͼ½â£º

ΪÁ˸üºÃµÄÀí½â£¬ÎÒ¼ÙÉ軺³åÇøÀïµÄÊý¾ÝûÓб»ãÅËøËø×¡£¨¾ÍÊÇ˵ÊÇ¿ÉÒÔ±»ÒƳýµÄ£©¡£ÔÚÕâ¸ö¼òµ¥µÄÀý×ÓÀ»º³åÇø¿ÉÒÔ±£´æ 3 ¸öÔªËØ£º

1£º»º´æ¹ÜÀíÆ÷£¨¼ò³ÆCM£©Ê¹ÓÃÊý¾Ý1£¬°ÑËü·ÅÈë¿ÕµÄ»º³åÇø

2£ºCMʹÓÃÊý¾Ý4£¬°ÑËü·ÅÈë°ëÔØµÄ»º³åÇø

3£ºCMʹÓÃÊý¾Ý3£¬°ÑËü·ÅÈë°ëÔØµÄ»º³åÇø

4£ºCMʹÓÃÊý¾Ý9£¬»º³åÇøÂúÁË£¬ËùÒÔÊý¾Ý1±»Çå³ý£¬ÒòΪËüÊÇ×îºóÒ»¸ö×î½üʹÓõģ¬Êý¾Ý9¼ÓÈëµ½»º³åÇø

5£ºCMʹÓÃÊý¾Ý4£¬Êý¾Ý4ÒѾ­ÔÚ»º³åÇøÁË£¬ËùÒÔËüÔٴγÉΪµÚÒ»¸ö×î½üʹÓõġ£

6£ºCMʹÓÃÊý¾Ý1£¬»º³åÇøÂúÁË£¬ËùÒÔÊý¾Ý9±»Çå³ý£¬ÒòΪËüÊÇ×îºóÒ»¸ö×î½üʹÓõģ¬Êý¾Ý1¼ÓÈëµ½»º³åÇø

¡­¡­

Õâ¸öË㷨Ч¹ûºÜºÃ£¬µ«ÊÇÓÐЩÏÞÖÆ¡£Èç¹û¶ÔÒ»¸ö´ó±íÖ´ÐÐÈ«±íɨÃèÔõô°ì£¿»»¾ä»°Ëµ£¬µ±±í/Ë÷ÒýµÄ´óС³¬³ö»º³åÇø»á·¢Éúʲô£¿Ê¹ÓÃÕâ¸öËã·¨»áÇå³ý֮ǰ»º´æÄÚËùÓеÄÊý¾Ý£¬¶øÇÒȫɨÃèµÄÊý¾ÝºÜ¿ÉÄÜֻʹÓÃÒ»´Î¡£

¸Ä½ø

ΪÁË·ÀÖ¹Õâ¸öÏÖÏó£¬ÓÐЩÊý¾Ý¿âÔö¼ÓÁËÌØÊâµÄ¹æÔò£¬±ÈÈçOracleÎĵµÖеÄÃèÊö£º

¡º¶Ô·Ç³£´óµÄ±íÀ´Ëµ£¬Êý¾Ý¿âͨ³£Ê¹ÓÃÖ±½Ó·¾¶À´¶ÁÈ¡£¬¼´Ö±½Ó¼ÓÔØÇø¿é[¡­¡­]£¬À´±ÜÃâÌîÂú»º³åÇø¡£¶ÔÓÚÖеȴóСµÄ±í£¬Êý¾Ý¿â¿ÉÒÔʹÓÃÖ±½Ó¶ÁÈ¡»ò»º´æ¶ÁÈ¡¡£Èç¹ûÑ¡Ôñ»º´æ¶ÁÈ¡£¬Êý¾Ý¿â°ÑÇø¿éÖÃÓÚLRUµÄβ²¿£¬·ÀÖ¹Çå¿Õµ±Ç°»º³åÇø¡£¡»

»¹ÓÐһЩ¿ÉÄÜ£¬±ÈÈçʹÓø߼¶°æ±¾µÄLRU£¬½Ð×ö LRU-K¡£ÀýÈ磬SQL Server ʹÓà LRU-2¡£

Õâ¸öËã·¨µÄÔ­ÀíÊǰѸü¶àµÄÀúÊ·¼Ç¼¿¼ÂǽøÀ´¡£¼òµ¥LRU£¨Ò²¾ÍÊÇ LRU-1£©£¬Ö»¿¼ÂÇ×îºóÒ»´ÎʹÓõÄÊý¾Ý¡£LRU-KÄØ£º

¿¼ÂÇÊý¾Ý×îºóµÚK´ÎʹÓõÄÇé¿ö

Êý¾ÝʹÓõĴÎÊý¼Ó½øÁËÈ¨ÖØ

Ò»ÅúÐÂÊý¾Ý¼ÓÔØ½øÈ뻺´æ£¬¾ÉµÄµ«ÊǾ­³£Ê¹ÓõÄÊý¾Ý²»»á±»Çå³ý£¨ÒòÎªÈ¨ÖØ¸ü¸ß£©

µ«ÊÇÕâ¸öËã·¨²»»á±£Áô»º´æÖв»ÔÙʹÓõÄÊý¾Ý

ËùÒÔÊý¾ÝÈç¹û²»ÔÙʹÓã¬È¨ÖØÖµËæ×Åʱ¼äÍÆÒÆ¶ø½µµÍ

¼ÆËãÈ¨ÖØÊÇÐèÒª³É±¾µÄ£¬ËùÒÔSQL ServerÖ»ÊÇʹÓà K=2£¬Õâ¸öÖµÐÔÄܲ»´í¶øÇÒ¶îÍ⿪Ïú¿ÉÒÔ½ÓÊÜ¡£

¹ØÓÚLRU-K¸üÉîÈëµÄ֪ʶ£¬¿ÉÒÔÔĶÁÔçÆÚµÄÑо¿ÂÛÎÄ£¨1993£©£ºÊý¾Ý¿â´ÅÅÌ»º³åµÄLRU-KÒ³ÃæÖû»Ëã·¨

ÆäËûËã·¨

µ±È»»¹ÓÐÆäËû¹ÜÀí»º´æµÄËã·¨£¬±ÈÈ磺

2Q£¨ÀàLRU-KËã·¨£©

CLOCK£¨ÀàLRU-KËã·¨£©

MRU£¨×îÐÂʹÓõÄËã·¨£¬ÓÃLRUͬÑùµÄÂß¼­µ«²»Í¬µÄ¹æÔò£©

LRFU£¨Least Recently and Frequently Used£¬×î½ü×îÉÙʹÓÃ×î½ü×î²»³£Óã©

¡­¡­

д»º³åÇø

ÎÒֻ̽ÌÖÁ˶Á»º´æ ¡ª¡ª ÔÚʹÓÃ֮ǰԤÏȼÓÔØÊý¾Ý¡£ÓÃÀ´±£´æÊý¾Ý¡¢³ÉÅúË¢Èë´ÅÅÌ£¬¶ø²»ÊÇÖðÌõдÈëÊý¾Ý´Ó¶øÔì³ÉºÜ¶àµ¥´Î´ÅÅÌ·ÃÎÊ¡£

Òª¼Çס£¬»º³åÇø±£´æµÄÊÇÒ³£¨×îСµÄÊý¾Ýµ¥Î»£©¶ø²»ÊÇÐУ¨Âß¼­ÉÏ/ÈËÀàϰ¹ßµÄ¹Û²ìÊý¾ÝµÄ·½Ê½£©¡£»º³å³ØÄÚµÄÒ³Èç¹û±»ÐÞ¸ÄÁ˵«»¹Ã»ÓÐдÈë´ÅÅÌ£¬¾ÍÊÇÔàÒ³¡£ÓкܶàËã·¨À´¾ö¶¨Ð´ÈëÔàÒ³µÄ×î¼Ñʱ»ú£¬µ«Õâ¸öÎÊÌâÓëÊÂÎñµÄ¸ÅÄî¸ß¶È¹ØÁª£¬ÏÂÃæÎÒÃǾÍ̸̸ÊÂÎñ¡£

ÊÂÎñ¹ÜÀíÆ÷

×îºóµ«Í¬ÑùÖØÒªµÄ£¬ÊÇÊÂÎñ¹ÜÀíÆ÷£¬ÎÒÃǽ«¿´µ½Õâ¸ö½ø³ÌÊÇÈçºÎ±£Ö¤Ã¿¸ö²éѯÔÚ×Ô¼ºµÄÊÂÎñÄÚÖ´Ðеġ£µ«¿ªÊ¼Ö®Ç°£¬ÎÒÃÇÐèÒªÀí½âACIDÊÂÎñµÄ¸ÅÄî¡£

¡°I¡¯m on acid¡±

Ò»¸öACIDÊÂÎñÊÇÒ»¸ö¹¤×÷µ¥Ôª£¬ËüÒª±£Ö¤4¸öÊôÐÔ£º

Ô­×ÓÐÔ£¨Atomicity£©: ÊÂÎñ¡ºÒªÃ´È«²¿Íê³É£¬ÒªÃ´È«²¿È¡Ïû¡»£¬¼´Ê¹Ëü³ÖÐøÔËÐÐ10¸öСʱ¡£Èç¹ûÊÂÎñ±ÀÀ££¬×´Ì¬»Øµ½ÊÂÎñ֮ǰ£¨ÊÂÎñ»Ø¹ö£©¡£

¸ôÀëÐÔ£¨Isolation£©: Èç¹û2¸öÊÂÎñ A ºÍ B ͬʱÔËÐУ¬ÊÂÎñ A ºÍ B ×îÖյĽá¹ûÊÇÏàͬµÄ£¬²»¹Ü A ÊǽáÊøÓÚ B ֮ǰ/Ö®ºó/ÔËÐÐÆÚ¼ä¡£

³Ö¾ÃÐÔ£¨Durability£©: Ò»µ©ÊÂÎñÌá½»£¨Ò²¾ÍÊdzɹ¦Ö´ÐУ©,²»¹Ü·¢Éúʲô£¨±ÀÀ£»òÕß³ö´í£©£¬Êý¾ÝÒª±£´æÔÚÊý¾Ý¿âÖС£

Ò»ÖÂÐÔ£¨Consistency£©: Ö»ÓкϷ¨µÄÊý¾Ý£¨ÒÀÕÕ¹ØÏµÔ¼ÊøºÍº¯ÊýÔ¼Êø£©ÄÜдÈëÊý¾Ý¿â£¬Ò»ÖÂÐÔÓëÔ­×ÓÐԺ͸ôÀëÐÔÓйء£

ÔÚͬһ¸öÊÂÎñÄÚ£¬Äã¿ÉÒÔÔËÐжà¸öSQL²éѯÀ´¶ÁÈ¡¡¢´´½¨¡¢¸üкÍɾ³ýÊý¾Ý¡£µ±Á½¸öÊÂÎñʹÓÃÏàͬµÄÊý¾Ý£¬Âé·³¾ÍÀ´ÁË¡£¾­µäµÄÀý×ÓÊÇ´ÓÕË»§Aµ½ÕË»§BµÄ»ã¿î¡£¼ÙÉèÓÐ2¸öÊÂÎñ£º

ÊÂÎñ1£¨T1£©´ÓÕË»§AÈ¡³ö100ÃÀÔª¸øÕË»§B

ÊÂÎñ2£¨T2£©´ÓÕË»§AÈ¡³ö50ÃÀÔª¸øÕË»§B

ÎÒÃÇ»ØÀ´¿´¿´ACIDÊôÐÔ£º

Ô­×ÓÐÔÈ·±£²»¹Ü T1 ÆÚ¼ä·¢Éúʲô£¨·þÎñÆ÷±ÀÀ£¡¢ÍøÂçÖжϡ­£©£¬Äã²»ÄܳöÏÖÕË»§A È¡×ßÁË100ÃÀÔªµ«Ã»ÓиøÕË»§B µÄÏÖÏó£¨Õâ¾ÍÊÇÊý¾Ý²»Ò»ÖÂ״̬£©¡£

¸ôÀëÐÔÈ·±£Èç¹û T1 ºÍ T2 ͬʱ·¢Éú£¬×îÖÕA½«¼õÉÙ150ÃÀÔª£¬B½«µÃµ½150ÃÀÔª£¬¶ø²»ÊÇÆäËû½á¹û£¬±ÈÈçÒòΪ T2 ²¿·ÖĨ³ýÁË T1 µÄÐÐΪ£¬A¼õÉÙ150ÃÀÔª¶øBÖ»µÃµ½50ÃÀÔª£¨ÕâÒ²ÊDz»Ò»ÖÂ״̬£©¡£

³Ö¾ÃÐÔÈ·±£Èç¹û T1 ¸Õ¸ÕÌá½»£¬Êý¾Ý¿â¾Í·¢Éú±ÀÀ££¬T1 ²»»áÏûʧµÃÎÞÓ°ÎÞ×Ù¡£

Ò»ÖÂÐÔÈ·±£Ç®²»»áÔÚϵͳÄÚÉú³É»òÃðʧ¡£

[ÒÔϲ¿·Ö²»ÖØÒª£¬¿ÉÒÔÌø¹ý]

ÏÖ´úÊý¾Ý¿â²»»áʹÓô¿´âµÄ¸ôÀë×÷ΪĬÈÏģʽ£¬ÒòΪËü»á´øÀ´¾Þ´óµÄÐÔÄÜÏûºÄ¡£SQLÒ»°ã¶¨Òå4¸ö¸ôÀë¼¶±ð£º

´®Ðл¯(Serializable£¬SQLiteĬÈÏģʽ£©£º×î¸ß¼¶±ðµÄ¸ôÀë¡£Á½¸öͬʱ·¢ÉúµÄÊÂÎñ100%¸ôÀ룬ÿ¸öÊÂÎñÓÐ×Ô¼ºµÄ¡ºÊÀ½ç¡»¡£

¿ÉÖØ¸´¶Á£¨Repeatable read£¬MySQLĬÈÏģʽ£©£ºÃ¿¸öÊÂÎñÓÐ×Ô¼ºµÄ¡ºÊÀ½ç¡»£¬³ýÁËÒ»ÖÖÇé¿ö¡£Èç¹ûÒ»¸öÊÂÎñ³É¹¦Ö´Ðв¢ÇÒÌí¼ÓÁËÐÂÊý¾Ý£¬ÕâЩÊý¾Ý¶ÔÆäËûÕýÔÚÖ´ÐеÄÊÂÎñÊǿɼûµÄ¡£µ«ÊÇÈç¹ûÊÂÎñ³É¹¦ÐÞ¸ÄÁËÒ»ÌõÊý¾Ý£¬Ð޸Ľá¹û¶ÔÕýÔÚÔËÐеÄÊÂÎñ²»¿É¼û¡£ËùÒÔ£¬ÊÂÎñÖ®¼äÖ»ÊÇÔÚÐÂÊý¾Ý·½ÃæÍ»ÆÆÁ˸ôÀ룬¶ÔÒÑ´æÔÚµÄÊý¾ÝÈԾɸôÀë¡£

¾Ù¸öÀý×Ó£¬Èç¹ûÊÂÎñAÔËÐС±SELECT count(1) from TABLE_X¡± £¬È»ºóÊÂÎñBÔÚ TABLE_X ¼ÓÈëÒ»ÌõÐÂÊý¾Ý²¢Ìá½»£¬µ±ÊÂÎñAÔÙÔËÐÐÒ»´Î count(1)½á¹û²»»áÊÇÒ»ÑùµÄ¡£

Õâ½Ð»Ã¶Á£¨phantom read£©¡£

¶ÁÈ¡ÒÑÌá½»£¨Read committed£¬Oracle¡¢PostgreSQL¡¢SQL ServerĬÈÏģʽ£©£º¿ÉÖØ¸´¶Á+еĸôÀëÍ»ÆÆ¡£Èç¹ûÊÂÎñA¶ÁÈ¡ÁËÊý¾ÝD£¬È»ºóÊý¾ÝD±»ÊÂÎñBÐ޸썻òɾ³ý£©²¢Ìá½»£¬ÊÂÎñAÔٴζÁÈ¡Êý¾ÝDʱÊý¾ÝµÄ±ä»¯£¨»òɾ³ý£©ÊǿɼûµÄ¡£

Õâ½Ð²»¿ÉÖØ¸´¶Á£¨non-repeatable read£©¡£

¶ÁȡδÌá½»£¨Read uncommitted£©£º×îµÍ¼¶±ðµÄ¸ôÀ룬ÊǶÁÈ¡ÒÑÌá½»+еĸôÀëÍ»ÆÆ¡£Èç¹ûÊÂÎñA¶ÁÈ¡ÁËÊý¾ÝD£¬È»ºóÊý¾ÝD±»ÊÂÎñBÐ޸썵«²¢Î´Ìá½»£¬ÊÂÎñBÈÔÔÚÔËÐÐÖУ©£¬ÊÂÎñAÔٴζÁÈ¡Êý¾ÝDʱ£¬Êý¾ÝÐÞ¸ÄÊǿɼûµÄ¡£Èç¹ûÊÂÎñB»Ø¹ö£¬ÄÇôÊÂÎñAµÚ¶þ´Î¶ÁÈ¡µÄÊý¾ÝDÊÇÎÞÒâÒåµÄ£¬ÒòΪÄÇÊÇÊÂÎñBËù×öµÄ´Óδ·¢ÉúµÄÐ޸ģ¨ÒѾ­»Ø¹öÁËÂ¡£

Õâ½ÐÔà¶Á£¨dirty read£©¡£

¶àÊýÊý¾Ý¿âÌí¼ÓÁË×Ô¶¨ÒåµÄ¸ôÀë¼¶±ð£¨±ÈÈç PostgreSQL¡¢Oracle¡¢SQL ServerµÄ¿ìÕÕ¸ôÀ룩£¬¶øÇÒ²¢Ã»ÓÐʵÏÖSQL¹æ·¶ÀïµÄËùÓм¶±ð£¨ÓÈÆäÊǶÁȡδÌá½»¼¶±ð£©¡£

ĬÈϵĸôÀë¼¶±ð¿ÉÒÔÓÉÓû§/¿ª·¢ÕßÔÚ½¨Á¢Á¬½Óʱ¸²¸Ç£¨Ö»ÐèÒªÔö¼ÓºÜ¼òµ¥µÄÒ»ÐдúÂ룩¡£

²¢·¢¿ØÖÆ

È·±£¸ôÀëÐÔ¡¢Ò»ÖÂÐÔºÍÔ­×ÓÐÔµÄÕæÕýÎÊÌâÊǶÔÏàͬÊý¾ÝµÄд²Ù×÷£¨Ôö¡¢¸ü¡¢É¾£©£º

Èç¹ûËùÓÐÊÂÎñÖ»ÊǶÁÈ¡Êý¾Ý£¬ËüÃÇ¿ÉÒÔͬʱ¹¤×÷£¬²»»á¸ü¸ÄÁíÒ»¸öÊÂÎñµÄÐÐΪ¡£

Èç¹û£¨ÖÁÉÙ£©ÓÐÒ»¸öÊÂÎñÔÚÐÞ¸ÄÆäËûÊÂÎñ¶ÁÈ¡µÄÊý¾Ý£¬Êý¾Ý¿âÐèÒªÕÒ¸ö°ì·¨¶ÔÆäËüÊÂÎñÒþ²ØÕâÖÖÐ޸ġ£¶øÇÒ£¬Ëü»¹ÐèҪȷ±£Õâ¸öÐ޸IJÙ×÷²»»á±»ÁíÒ»¸ö¿´²»µ½ÕâЩÊý¾ÝÐ޸ĵÄÊÂÎñ²Á³ý¡£

Õâ¸öÎÊÌâ½Ð²¢·¢¿ØÖÆ¡£

×î¼òµ¥µÄ½â¾ö°ì·¨ÊÇÒÀ´ÎÖ´ÐÐÿ¸öÊÂÎñ£¨¼´Ë³ÐòÖ´ÐУ©£¬µ«ÕâÑù¾ÍÍêȫûÓÐÉìËõÐÔÁË£¬ÔÚÒ»¸ö¶à´¦ÀíÆ÷/¶àºË·þÎñÆ÷ÉÏÖ»ÓÐÒ»¸öºËÐÄÔÚ¹¤×÷£¬Ð§Âʺܵ͡£

ÀíÏëµÄ°ì·¨ÊÇ£¬Ã¿´ÎÒ»¸öÊÂÎñ´´½¨»òÈ¡Ïûʱ£º

¼à¿ØËùÓÐÊÂÎñµÄËùÓвÙ×÷

¼ì²éÊÇ·ñ2¸ö£¨»ò¸ü¶à£©ÊÂÎñµÄ²¿·Ö²Ù×÷ÒòΪ¶ÁÈ¡/ÐÞ¸ÄÏàͬµÄÊý¾Ý¶ø´æÔÚ³åÍ»

ÖØÐ±àÅųåÍ»ÊÂÎñÖеIJÙ×÷À´¼õÉÙ³åÍ»µÄ²¿·Ö

°´ÕÕÒ»¶¨µÄ˳ÐòÖ´ÐгåÍ»µÄ²¿·Ö£¨Í¬Ê±·Ç³åÍ»ÊÂÎñÈÔÈ»ÔÚ²¢·¢ÔËÐУ©

¿¼ÂÇÊÂÎñÓпÉÄܱ»È¡Ïû

ÓøüÕý¹æµÄ˵·¨£¬ÕâÊǶԳåÍ»µÄµ÷¶ÈÎÊÌâ¡£¸ü¾ßÌåµã¶ù˵£¬ÕâÊǸö·Ç³£À§ÄѶøÇÒCPU¿ªÏúºÜ´óµÄÓÅ»¯ÎÊÌâ¡£ÆóÒµ¼¶Êý¾Ý¿âÎÞ·¨³Ðµ£µÈ´ý¼¸¸öСʱ£¬À´Ñ°ÕÒÿ¸öÐÂÊÂÎñ»î¶¯×îºÃµÄµ÷¶È£¬Òò´Ë¾ÍʹÓò»ÄÇôÀíÏëµÄ·½Ê½ÒÔ±ÜÃâ¸ü¶àµÄʱ¼äÀË·ÑÔÚ½â¾ö³åÍ»ÉÏ¡£

Ëø¹ÜÀíÆ÷

ΪÁ˽â¾öÕâ¸öÎÊÌ⣬¶àÊýÊý¾Ý¿âʹÓÃËøºÍ/»òÊý¾Ý°æ±¾¿ØÖÆ¡£ÕâÊǸöºÜ´óµÄ»°Ì⣬ÎһἯÖÐ̽ÌÖËø£¬ºÍÒ»µãµãÊý¾Ý°æ±¾¿ØÖÆ¡£

±¯¹ÛËø

Ô­ÀíÊÇ£º

Èç¹ûÒ»¸öÊÂÎñÐèÒªÒ»ÌõÊý¾Ý

Ëü¾Í°ÑÊý¾ÝËø×¡

Èç¹ûÁíÒ»¸öÊÂÎñÒ²ÐèÒªÕâÌõÊý¾Ý

Ëü¾Í±ØÐëÒªµÈµÚÒ»¸öÊÂÎñÊÍ·ÅÕâÌõÊý¾Ý

Õâ¸öËø½ÐÅÅËûËø¡£

µ«ÊǶÔÒ»¸ö½ö½ö¶ÁÈ¡Êý¾ÝµÄÊÂÎñʹÓÃÅÅËûËø·Ç³£°º¹ó£¬ÒòΪÕâ»áÆÈʹÆäËüÖ»ÐèÒª¶ÁÈ¡ÏàͬÊý¾ÝµÄÊÂÎñµÈ´ý¡£Òò´Ë¾ÍÓÐÁËÁíÒ»ÖÖËø£¬¹²ÏíËø¡£

¹²ÏíËøÊÇÕâÑùµÄ£º

Èç¹ûÒ»¸öÊÂÎñÖ»ÐèÒª¶ÁÈ¡Êý¾ÝA

Ëü»á¸øÊý¾ÝA¼ÓÉÏ¡º¹²ÏíËø¡»²¢¶ÁÈ¡

Èç¹ûµÚ¶þ¸öÊÂÎñÒ²ÐèÒª½ö½ö¶ÁÈ¡Êý¾ÝA

Ëü»á¸øÊý¾ÝA¼ÓÉÏ¡º¹²ÏíËø¡»²¢¶ÁÈ¡

Èç¹ûµÚÈý¸öÊÂÎñÐèÒªÐÞ¸ÄÊý¾ÝA

Ëü»á¸øÊý¾ÝA¼ÓÉÏ¡ºÅÅËûËø¡»£¬µ«ÊDZØÐëµÈ´ýÁíÍâÁ½¸öÊÂÎñÊÍ·ÅËüÃǵĹ²ÏíËø¡£

ͬÑùµÄ£¬Èç¹ûÒ»¿éÊý¾Ý±»¼ÓÉÏÅÅËûËø£¬Ò»¸öÖ»ÐèÒª¶ÁÈ¡¸ÃÊý¾ÝµÄÊÂÎñ±ØÐëµÈ´ýÅÅËûËøÊͷŲÅÄܸø¸ÃÊý¾Ý¼ÓÉϹ²ÏíËø¡£

Ëø¹ÜÀíÆ÷ÊÇÌí¼ÓºÍÊÍ·ÅËøµÄ½ø³Ì£¬ÔÚÄÚ²¿ÓÃÒ»¸ö¹þÏ£±í±£´æËøÐÅÏ¢£¨¹Ø¼ü×ÖÊDZ»ËøµÄÊý¾Ý£©£¬²¢ÇÒÁ˽âÿһ¿éÊý¾ÝÊÇ£º

±»ÄĸöÊÂÎñ¼ÓµÄËø

ÄĸöÊÂÎñÔڵȴýÊý¾Ý½âËø

ËÀËø

µ«ÊÇʹÓÃËø»áµ¼ÖÂÒ»ÖÖÇé¿ö£¬2¸öÊÂÎñÓÀÔ¶ÔڵȴýÒ»¿éÊý¾Ý£º

ÔÚ±¾Í¼ÖУº

ÊÂÎñA ¸ø Êý¾Ý1 ¼ÓÉÏÅÅËûËø²¢Çҵȴý»ñÈ¡Êý¾Ý2

ÊÂÎñB ¸ø Êý¾Ý2 ¼ÓÉÏÅÅËûËø²¢Çҵȴý»ñÈ¡Êý¾Ý1

Õâ½ÐËÀËø¡£

ÔÚËÀËø·¢Éúʱ£¬Ëø¹ÜÀíÆ÷ҪѡÔñÈ¡Ïû£¨»Ø¹ö£©Ò»¸öÊÂÎñ£¬ÒÔ±ãÏû³ýËÀËø¡£Õâ¿ÉÊǸö¼èÄѵľö¶¨£º

ɱËÀÊý¾ÝÐÞ¸ÄÁ¿×îÉÙµÄÊÂÎñ£¨ÕâÑùÄܼõÉٻعöµÄ³É±¾£©£¿

ɱËÀ³ÖÐøÊ±¼ä×î¶ÌµÄÊÂÎñ£¬ÒòΪÆäËüÊÂÎñµÄÓû§µÈµÄʱ¼ä¸ü³¤£¿

ɱËÀÄÜÓøüÉÙʱ¼ä½áÊøµÄÊÂÎñ£¨±ÜÃâ¿ÉÄܵÄ×ÊÔ´¼¢»Ä£©£¿

Ò»µ©·¢Éú»Ø¹ö£¬ÓжàÉÙÊÂÎñ»áÊܵ½»Ø¹öµÄÓ°Ï죿

ÔÚ×÷³öÑ¡Ôñ֮ǰ£¬Ëø¹ÜÀíÆ÷ÐèÒª¼ì²éÊÇ·ñÓÐËÀËø´æÔÚ¡£

¹þÏ£±í¿ÉÒÔ¿´×÷ÊǸöͼ±í£¨¼ûÉÏÎÄͼ£©£¬Í¼ÖгöÏÖÑ­»·¾Í˵Ã÷ÓÐËÀËø¡£ÓÉÓÚ¼ì²éÑ­»·Êǰº¹óµÄ£¨ËùÓÐËø×é³ÉµÄͼ±íÊǺÜÅÓ´óµÄ£©£¬¾­³£»áͨ¹ý¼òµ¥µÄ;¾¶½â¾ö£ºÊ¹Óó¬Ê±É趨¡£Èç¹ûÒ»¸öËøÔÚ³¬Ê±Ê±¼äÄÚûÓмÓÉÏ£¬ÄÇÊÂÎñ¾Í½øÈëËÀËø×´Ì¬¡£

Ëø¹ÜÀíÆ÷Ò²¿ÉÒÔÔÚ¼ÓËøÖ®Ç°¼ì²é¸ÃËø»á²»»á±ä³ÉËÀËø£¬µ«ÊÇÏëÒªÍêÃÀµÄ×öµ½ÕâÒ»µã»¹ÊǺܰº¹óµÄ¡£Òò´ËÕâЩԤ¼ì¾­³£ÉèÖÃһЩ»ù±¾¹æÔò¡£

Á½¶ÎËø

ʵÏÖ´¿´âµÄ¸ôÀë×î¼òµ¥µÄ·½·¨ÊÇ£ºÊÂÎñ¿ªÊ¼Ê±»ñÈ¡Ëø£¬½áÊøÊ±ÊÍ·ÅËø¡£¾ÍÊÇ˵£¬ÊÂÎñ¿ªÊ¼Ç°±ØÐëµÈ´ýÈ·±£×Ô¼ºÄܼÓÉÏËùÓеÄËø£¬µ±ÊÂÎñ½áÊøÊ±ÊÍ·Å×Ô¼º³ÖÓеÄËø¡£ÕâÊÇÐеÃͨµÄ£¬µ«ÊÇΪÁ˵ȴýËùÓеÄËø£¬´óÁ¿µÄʱ¼ä±»ÀË·ÑÁË¡£

¸ü¿ìµÄ·½·¨ÊÇÁ½¶ÎËøÐ­Ò飨Two-Phase Locking Protocol£¬ÓÉ DB2 ºÍ SQL ServerʹÓã©£¬ÔÚÕâÀÊÂÎñ·ÖΪÁ½¸ö½×¶Î£º

³É³¤½×¶Î£ºÊÂÎñ¿ÉÒÔ»ñµÃËø£¬µ«²»ÄÜÊÍ·ÅËø¡£

ÊÕËõ½×¶Î£ºÊÂÎñ¿ÉÒÔÊÍ·ÅËø£¨¶ÔÓÚÒѾ­´¦ÀíÍê¶øÇÒ²»»áÔٴδ¦ÀíµÄÊý¾Ý£©£¬µ«²»ÄÜ»ñµÃÐÂËø¡£

ÕâÁ½Ìõ¼òµ¥¹æÔò±³ºóµÄÔ­ÀíÊÇ£º

ÊͷŲ»ÔÙʹÓõÄËø£¬À´½µµÍÆäËüÊÂÎñµÄµÈ´ýʱ¼ä

·ÀÖ¹·¢ÉúÕâÀàÇé¿ö£ºÊÂÎñ×î³õ»ñµÃµÄÊý¾Ý£¬ÔÚÊÂÎñ¿ªÊ¼ºó±»Ð޸쬵±ÊÂÎñÖØÐ¶ÁÈ¡¸ÃÊý¾Ýʱ·¢Éú²»Ò»Ö¡£

Õâ¸ö¹æÔò¿ÉÒԺܺõع¤×÷£¬µ«ÓиöÀýÍ⣺Èç¹ûÐÞ¸ÄÁËÒ»ÌõÊý¾Ý¡¢ÊÍ·ÅÁ˹ØÁªµÄËøºó£¬ÊÂÎñ±»È¡Ïû£¨»Ø¹ö£©£¬¶øÁíÒ»¸öÊÂÎñ¶Áµ½ÁËÐ޸ĺóµÄÖµ£¬µ«×îºóÕâ¸öֵȴ±»»Ø¹ö¡£ÎªÁ˱ÜÃâÕâ¸öÎÊÌ⣬ËùÓжÀÕ¼Ëø±ØÐëÔÚÊÂÎñ½áÊøÊ±ÊÍ·Å¡£

¶à˵¼¸¾ä

µ±È»ÁË£¬ÕæÊµµÄÊý¾Ý¿âʹÓøü¸´ÔÓµÄϵͳ£¬Éæ¼°µ½¸ü¶àÀàÐ͵ÄËø£¨±ÈÈçÒâÏòËø£¬intention locks£©ºÍ¸ü¶àµÄÁ£¶È£¨Ðм¶Ëø¡¢Ò³¼¶Ëø¡¢·ÖÇøËø¡¢±íËø¡¢±í¿Õ¼äËø£©£¬µ«ÊǵÀÀíÊÇÏàͬµÄ¡£

ÎÒֻ̽ÌÖ´¿´â»ùÓÚËøµÄ·½·¨£¬Êý¾Ý°æ±¾¿ØÖÆÊǽâ¾öÕâ¸öÎÊÌâµÄÁíÒ»¸ö·½·¨¡£

°æ±¾¿ØÖÆÊÇÕâÑùµÄ£º

ÿ¸öÊÂÎñ¿ÉÒÔÔÚÏàͬʱ¿ÌÐÞ¸ÄÏàͬµÄÊý¾Ý

ÿ¸öÊÂÎñÓÐ×Ô¼ºµÄÊý¾Ý¿½±´£¨»òÕ߽а汾£©

Èç¹û2¸öÊÂÎñÐÞ¸ÄÏàͬµÄÊý¾Ý£¬Ö»½ÓÊÜÒ»¸öÐ޸ģ¬ÁíÒ»¸ö½«±»¾Ü¾ø£¬Ïà¹ØµÄÊÂÎñ»Ø¹ö£¨»òÖØÐÂÔËÐУ©

Õ⽫Ìá¸ßÐÔÄÜ£¬ÒòΪ£º

¶ÁÊÂÎñ²»»á×èÈûдÊÂÎñ

дÊÂÎñ²»»á×èÈû¶Á

ûÓСºÓ·Ö×»ºÂý¡»µÄËø¹ÜÀíÆ÷´øÀ´µÄ¶îÍ⿪Ïú

³ýÁËÁ½¸öÊÂÎñдÏàͬÊý¾ÝµÄʱºò£¬Êý¾Ý°æ±¾¿ØÖƸ÷¸ö·½Ãæ¶¼±ÈËø±íÏֵøüºÃ¡£Ö»²»¹ý£¬ÄãºÜ¿ì¾Í»á·¢ÏÖ´ÅÅ̿ռäÏûºÄ¾Þ´ó¡£

Êý¾Ý°æ±¾¿ØÖƺÍËø»úÖÆÊÇÁ½ÖÖ²»Í¬µÄ¼û½â£ºÀÖ¹ÛËøºÍ±¯¹ÛËø¡£Á½Õ߸÷ÓÐÀû±×£¬Íêȫȡ¾öÓÚʹÓó¡¾°£¨¶Á¶à»¹ÊÇд¶à£©¡£¹ØÓÚÊý¾Ý°æ±¾¿ØÖÆ£¬ÎÒÍÆ¼öÕâÆª·Ç³£ÓÅÐãµÄÎÄÕ£¬½²µÄÊÇPostgreSQLÈçºÎʵÏÖ¶à°æ±¾²¢·¢¿ØÖƵġ£

һЩÊý¾Ý¿â£¬±ÈÈçDB2£¨Ö±µ½°æ±¾ 9.7£©ºÍ SQL Server£¨²»º¬¿ìÕÕ¸ôÀ룩½öʹÓÃËø»úÖÆ¡£ÆäËûµÄÏñPostgreSQL, MySQL ºÍ Oracle ʹÓÃËøºÍÊó±ê°æ±¾¿ØÖÆ»ìºÏ»úÖÆ¡£ÎÒ²»ÖªµÀÊÇ·ñÓнöÓð汾¿ØÖƵÄÊý¾Ý¿â£¨Èç¹ûÄãÖªµÀÇë¸æËßÎÒ£©¡£

[2015-08-20¸üÐÂ]Ò»Ãû¶ÁÕ߸æËßÎÒ£º

Firebird ºÍ Interbase Óò»´øËøµÄ°æ±¾¿ØÖÆ¡£

°æ±¾¿ØÖƶÔË÷ÒýµÄÓ°ÏìͦÓÐȤµÄ£ºÓÐʱΨһË÷Òý»á³öÏÖÖØ¸´£¬Ë÷ÒýµÄÌõÄ¿»á¶àÓÚ±íÐÐÊý£¬µÈµÈ¡£

Èç¹ûÄã¶Á¹ý²»Í¬¼¶±ðµÄ¸ôÀëÄDz¿·ÖÄÚÈÝ£¬Äã»áÖªµÀ£¬Ìá¸ß¸ôÀë¼¶±ð¾Í»áÔö¼ÓËøµÄÊýÁ¿ºÍÊÂÎñµÈ´ý¼ÓËøµÄʱ¼ä¡£Õâ¾ÍÊÇΪʲô¶àÊýÊý¾Ý¿âĬÈϲ»»áʹÓÃ×î¸ß¼¶±ðµÄ¸ôÀ루¼´´®Ðл¯£©¡£

µ±È»£¬Äã×ÜÊÇ¿ÉÒÔ×Ô¼ºÈ¥Ö÷Á÷Êý¾Ý¿â£¨ÏñMySQL, PostgreSQL »ò Oracle£©µÄÎĵµÀï²éһϡ£

ÈÕÖ¾¹ÜÀíÆ÷

ÎÒÃÇÒѾ­ÖªµÀ£¬ÎªÁËÌáÉýÐÔÄÜ£¬Êý¾Ý¿â°ÑÊý¾Ý±£´æÔÚÄڴ滺³åÇøÄÚ¡£µ«Èç¹ûµ±ÊÂÎñÌύʱ·þÎñÆ÷±ÀÀ££¬±ÀÀ£Ê±»¹ÔÚÄÚ´æÀïµÄÊý¾Ý»á¶ªÊ§£¬ÕâÆÆ»µÁËÊÂÎñµÄ³Ö¾ÃÐÔ¡£

Äã¿ÉÒÔ°ÑËùÓÐÊý¾Ý¶¼Ð´ÔÚ´ÅÅÌÉÏ£¬µ«ÊÇÈç¹û·þÎñÆ÷±ÀÀ££¬×îÖÕÊý¾Ý¿ÉÄÜÖ»Óв¿·ÖдÈë´ÅÅÌ£¬ÕâÆÆ»µÁËÊÂÎñµÄÔ­×ÓÐÔ¡£

ÊÂÎñ×÷³öµÄÈκÎÐ޸ıØÐëÊÇ»òÕß³·Ïú£¬»òÕßÍê³É¡£

ÓÐ 2 ¸ö°ì·¨½â¾öÕâ¸öÎÊÌ⣺

Ó°×Ó¸±±¾/Ò³£¨Shadow copies/pages£©£ºÃ¿¸öÊÂÎñ´´½¨×Ô¼ºµÄÊý¾Ý¿â¸±±¾£¨»ò²¿·ÖÊý¾Ý¿âµÄ¸±±¾£©£¬²¢»ùÓÚÕâ¸ö¸±±¾À´¹¤×÷¡£Ò»µ©³ö´í£¬Õâ¸ö¸±±¾¾Í±»ÒƳý£»Ò»µ©³É¹¦£¬Êý¾Ý¿âÁ¢¼´Ê¹ÓÃÎļþϵͳµÄÒ»¸ö°ÑÏ·£¬°Ñ¸±±¾Ìæ»»µ½Êý¾ÝÖУ¬È»ºóɾµô¡º¾É¡»Êý¾Ý¡£

ÊÂÎñÈÕÖ¾£¨Transaction log£©£ºÊÂÎñÈÕÖ¾ÊÇÒ»¸ö´æ´¢¿Õ¼ä£¬ÔÚÿ´ÎдÅÌ֮ǰ£¬Êý¾Ý¿âÔÚÊÂÎñÈÕÖ¾ÖÐдÈëһЩÐÅÏ¢£¬ÕâÑùµ±ÊÂÎñ±ÀÀ£»ò»Ø¹ö£¬Êý¾Ý¿âÖªµÀÈçºÎÒÆ³ý»òÍê³ÉÉÐδÍê³ÉµÄÊÂÎñ¡£

WAL£¨Ô¤Ð´Ê½ÈÕÖ¾£©

Ó°×Ó¸±±¾/Ò³ÔÚÔËÐн϶àÊÂÎñµÄ´óÐÍÊý¾Ý¿âÊ±ÖÆÔìÁË´óÁ¿´ÅÅÌ¿ªÏú£¬ËùÒÔÏÖ´úÊý¾Ý¿âʹÓÃÊÂÎñÈÕÖ¾¡£ÊÂÎñÈÕÖ¾±ØÐë±£´æÔÚÎȶ¨µÄ´æ´¢ÉÏ£¬ÎÒ²»»áÉîÍÚ´æ´¢¼¼Êõ£¬µ«ÖÁÉÙRAID´ÅÅÌÊDZØÐëµÄ£¬ÒÔ·À´ÅÅ̹ÊÕÏ¡£

¶àÊýÊý¾Ý¿â£¨ÖÁÉÙÊÇOracle, SQL Server, DB2, PostgreSQL, MySQL ºÍ SQLite) ʹÓÃԤдÈÕ־ЭÒ飨Write-Ahead Logging protocol £¬WAL£©À´´¦ÀíÊÂÎñÈÕÖ¾¡£WALЭÒéÓÐ 3 ¸ö¹æÔò£º

1) ÿ¸ö¶ÔÊý¾Ý¿âµÄÐ޸ͼ²úÉúÒ»ÌõÈÕÖ¾¼Ç¼£¬ÔÚÊý¾ÝдÈë´ÅÅÌ֮ǰÈÕÖ¾¼Ç¼±ØÐëдÈëÊÂÎñÈÕÖ¾¡£

2) ÈÕÖ¾¼Ç¼±ØÐ밴˳ÐòдÈ룻¼Ç¼ A ·¢ÉúÔڼǼ B ֮ǰ£¬Ôò A ±ØÐëдÔÚ B ֮ǰ¡£

3) µ±Ò»¸öÊÂÎñÌύʱ£¬ÔÚÊÂÎñ³É¹¦Ö®Ç°£¬Ìύ˳Ðò±ØÐëдÈëµ½ÊÂÎñÈÕÖ¾¡£

Õâ¸ö¹¤×÷ÓÉÈÕÖ¾¹ÜÀíÆ÷Íê³É¡£¼òµ¥µÄÀí½â¾ÍÊÇ£¬ÈÕÖ¾¹ÜÀíÆ÷´¦ÓÚ»º´æ¹ÜÀíÆ÷£¨cache manager£©ºÍÊý¾Ý·ÃÎʹÜÀíÆ÷£¨data access manager£¬¸ºÔð°ÑÊý¾ÝдÈë´ÅÅÌ£©Ö®¼ä£¬Ã¿¸ö update / delete / create / commit / rollback ²Ù×÷ÔÚдÈë´ÅÅÌ֮ǰÏÈдÈëÊÂÎñÈÕÖ¾¡£¼òµ¥£¬¶Ô°É£¿

»Ø´ð´íÎó£¡ ÎÒÃÇÑо¿ÁËÕâô¶àÄÚÈÝ£¬ÏÖÔÚÄãÓ¦¸ÃÖªµÀÓëÊý¾Ý¿âÏà¹ØµÄÿһ¼þʶ¼´ø×Å¡ºÊý¾Ý¿âЧӦ¡»µÄ×çÖä¡£ºÃ°É£¬ÎÒÃÇ˵Õý¾­µÄ£¬ÎÊÌâÔÚÓÚ£¬ÈçºÎÕÒµ½Ð´ÈÕÖ¾µÄͬʱ±£³ÖÁ¼ºÃµÄÐÔÄܵķ½·¨¡£Èç¹ûÊÂÎñÈÕ־дµÃÌ«Âý£¬ÕûÌå¶¼»áÂýÏÂÀ´¡£

ARIES

1992Ä꣬IBM Ñо¿ÈËÔ±¡º·¢Ã÷¡»ÁËWALµÄÔöÇ¿°æ£¬½Ð ARIES¡£ARIES »ò¶à»òÉÙµØÔÚÏÖ´úÊý¾Ý¿âÖÐʹÓã¬Âß¼­Î´±ØÏàͬ£¬µ«AIRES±³ºóµÄ¸ÅÄîÎÞ´¦²»ÔÚ¡£ÎÒ¸ø·¢Ã÷¼ÓÁËÒýºÅÊÇÒòΪ£¬°´ÕÕMITÕâÃſεÄ˵·¨£¬IBM µÄÑо¿ÈËÔ±¡º½ö½öÊÇдÁËÊÂÎñ»Ö¸´µÄ×î¼Ñʵ¼ù·½·¨¡»¡£AIRES ÂÛÎÄ·¢±íµÄʱºòÎҲŠ5 Ë꣬ÎÒ²»¹ØÐÄÄÇЩËáÁïÁïµÄ¿ÆÑÐÈËÔ±ÀϵôÑÀµÄÏÐÑÔËéÓï¡£ÊÂʵÉÏ£¬ÎÒÌá¼°Õâ¸öµä¹Ê£¬ÊÇÔÚ¿ªÊ¼Ì½ÌÖ×îºóÒ»¸ö¼¼ÊõµãǰÈÃÄãÇáËÉһϡ£ÎÒÔĶÁ¹ýÕâÆª ARIES ÂÛÎÄ µÄ´óÁ¿Æª·ù£¬·¢ÏÖËüºÜÓÐȤ¡£ÔÚÕâÒ»²¿·ÖÎÒÖ»ÊǼòÒªµÄ̸һÏ ARIES£¬²»¹ýÎÒÇ¿ÁÒ½¨Ò飬Èç¹ûÄãÏëÁ˽âÕæÕýµÄ֪ʶ£¬¾ÍÈ¥¶ÁÄÇÆªÂÛÎÄ¡£

ARIES ´ú±í¡ºÊý¾Ý¿â»Ö¸´Ô­ÐÍËã·¨¡»£¨Algorithms for Recovery and Isolation Exploiting Semantics£©¡£

Õâ¸ö¼¼ÊõÒª´ïµ½Ò»¸öË«ÖØÄ¿±ê£º

1) дÈÕÖ¾µÄͬʱ±£³ÖÁ¼ºÃÐÔÄÜ

2) ¿ìËٺͿɿ¿µÄÊý¾Ý»Ö¸´

Óжà¸öÔ­ÒòÈÃÊý¾Ý¿â²»µÃ²»»Ø¹öÊÂÎñ£º

ÒòΪÓû§È¡Ïû

ÒòΪ·þÎñÆ÷»òÍøÂç¹ÊÕÏ

ÒòΪÊÂÎñÆÆ»µÁËÊý¾Ý¿âÍêÕûÐÔ£¨±ÈÈçÒ»¸öÁÐÓÐΨһÐÔÔ¼Êø¶øÊÂÎñÌí¼ÓÁËÖØ¸´Öµ£©

ÒòΪËÀËø

ÓÐʱºò£¨±ÈÈçÍøÂç³öÏÖ¹ÊÕÏ£©£¬Êý¾Ý¿â¿ÉÒÔ»Ö¸´ÊÂÎñ¡£

ÕâÔõô¿ÉÄÜÄØ£¿ÎªÁ˻شðÕâ¸öÎÊÌ⣬ÎÒÃÇÐèÒªÁ˽âÈÕÖ¾Àï±£´æµÄÐÅÏ¢¡£

ÈÕÖ¾

ÊÂÎñµÄÿһ¸ö²Ù×÷£¨Ôö/ɾ/¸Ä£©²úÉúÒ»ÌõÈÕÖ¾£¬ÓÉÈçÏÂÄÚÈÝ×é³É£º

LSN£ºÒ»¸öΨһµÄÈÕÖ¾ÐòÁкţ¨Log Sequence Number£©¡£LSNÊǰ´Ê±¼ä˳Ðò·ÖÅäµÄ * £¬ÕâÒâζ×ÅÈç¹û²Ù×÷ A ÏÈÓÚ²Ù×÷ B£¬log A µÄ LSN Òª±È log B µÄ LSN С¡£

TransID£º²úÉú²Ù×÷µÄÊÂÎñID¡£

PageID£º±»Ð޸ĵÄÊý¾ÝÔÚ´ÅÅÌÉϵÄλÖᣴÅÅÌÊý¾ÝµÄ×îСµ¥Î»ÊÇÒ³£¬ËùÒÔÊý¾ÝµÄλÖþÍÊÇËüËù´¦Ò³µÄλÖá£

PrevLSN£ºÍ¬Ò»¸öÊÂÎñ²úÉúµÄÉÏÒ»ÌõÈÕÖ¾¼Ç¼µÄÁ´½Ó¡£

UNDO£ºÈ¡Ïû±¾´Î²Ù×÷µÄ·½·¨¡£

±ÈÈ磬Èç¹û²Ù×÷ÊÇÒ»´Î¸üУ¬UNDO½«»òÕß±£´æÔªËظüÐÂǰµÄÖµ/״̬£¨ÎïÀíUNDO£©£¬»òÕ߻ص½Ô­À´×´Ì¬µÄ·´Ïò²Ù×÷£¨Âß¼­UNDO£© **¡£

REDO£ºÖظ´±¾´Î²Ù×÷µÄ·½·¨¡£ ͬÑùµÄ£¬ÓÐ 2 ÖÖ·½·¨£º»òÕß±£´æ²Ù×÷ºóµÄÔªËØÖµ/״̬£¬»òÕß±£´æ²Ù×÷±¾ÉíÒÔ±ãÖØ¸´¡£

¡­£º£¨¹©Äú²Î¿¼£¬Ò»¸ö ARIES ÈÕÖ¾»¹ÓÐ 2 ¸ö×ֶΣºUndoNxtLSN ºÍ Type£©¡£

½øÒ»²½Ëµ£¬´ÅÅÌÉÏÿ¸öÒ³£¨±£´æÊý¾ÝµÄ£¬²»ÊDZ£´æÈÕÖ¾µÄ£©¶¼¼Ç¼×Å×îºóÒ»¸öÐ޸ĸÃÊý¾Ý²Ù×÷µÄLSN¡£

*LSNµÄ·ÖÅäÆäʵ¸ü¸´ÔÓ£¬ÒòΪËü¹ØÏµµ½ÈÕÖ¾´æ´¢µÄ·½Ê½¡£µ«µÀÀíÊÇÏàͬµÄ¡£

** ARIES ֻʹÓÃÂß¼­UNDO£¬ÒòΪ´¦ÀíÎïÀíUNDOÌ«¹ý»ìÂÒÁË¡£

×¢£º¾ÝÎÒËùÖª£¬Ö»ÓÐ PostgreSQL ûÓÐʹÓÃUNDO£¬¶øÊÇÓÃÒ»¸öÀ¬»ø»ØÊÕ·þÎñÀ´É¾³ý¾É°æ±¾µÄÊý¾Ý¡£Õâ¸ö¸ú PostgreSQL ¶ÔÊý¾Ý°æ±¾¿ØÖƵÄʵÏÖÓйء£

ΪÁ˸üºÃµÄ˵Ã÷ÕâÒ»µã£¬ÕâÓÐÒ»¸ö¼òµ¥µÄÈÕÖ¾¼Ç¼ÑÝʾͼ£¬ÊÇÓɲéѯ ¡°UPDATE FROM PERSON SET AGE = 18;¡± ²úÉúµÄ£¬ÎÒÃǼÙÉèÕâ¸ö²éѯÊÇÊÂÎñ18Ö´Ðеġ£¡¾ÒëÕß×¢£º SQL Óï¾äÔ­ÎÄÈç´Ë£¬Ó¦¸ÃÊÇ×÷Õß±ÊÎó ¡¿

ÿÌõÈÕÖ¾¶¼ÓÐÒ»¸öΨһµÄLSN£¬Á´½ÓÔÚÒ»ÆðµÄÈÕÖ¾ÊôÓÚͬһ¸öÊÂÎñ¡£ÈÕÖ¾°´ÕÕʱ¼ä˳ÐòÁ´½Ó£¨Á´½ÓÁбíµÄ×îºóÒ»ÌõÈÕÖ¾ÊÇ×îºóÒ»¸ö²Ù×÷²úÉúµÄ£©¡£

ÈÕÖ¾»º³åÇø

ΪÁË·ÀֹдÈÕÖ¾³ÉΪÖ÷ÒªµÄÆ¿¾±£¬Êý¾Ý¿âʹÓÃÁËÈÕÖ¾»º³åÇø¡£

µ±²éѯִÐÐÆ÷ÒªÇó×öÒ»´ÎÐ޸ģº

1) »º´æ¹ÜÀíÆ÷½«Ð޸ĴæÈë×Ô¼ºµÄ»º³åÇø£»

2) ÈÕÖ¾¹ÜÀíÆ÷½«Ïà¹ØµÄÈÕÖ¾´æÈë×Ô¼ºµÄ»º³åÇø£»

3) µ½ÁËÕâÒ»²½£¬²éѯִÐÐÆ÷ÈÏΪ²Ù×÷Íê³ÉÁË£¨Òò´Ë¿ÉÒÔÇëÇó×öÁíÒ»´ÎÐ޸ģ©£»

4) ½Ó×Å£¨²»¾ÃÒÔºó£©ÈÕÖ¾¹ÜÀíÆ÷°ÑÈÕ־дÈëÊÂÎñÈÕÖ¾£¬Ê²Ã´Ê±ºòдÈÕÖ¾ÓÉijËã·¨À´¾ö¶¨¡£

5) ½Ó×Å£¨²»¾ÃÒԺ󣩻º´æ¹ÜÀíÆ÷°ÑÐÞ¸ÄдÈë´ÅÅÌ£¬Ê²Ã´Ê±ºòдÅÌÓÉijËã·¨À´¾ö¶¨¡£

µ±ÊÂÎñÌá½»£¬Òâζ×ÅÊÂÎñÿһ¸ö²Ù×÷µÄ 1 2 3 4 5 ²½Öè¶¼Íê³ÉÁË¡£Ð´ÊÂÎñÈÕÖ¾ÊǺܿìµÄ£¬ÒòΪËüÖ»ÊÇ¡ºÔÚÊÂÎñÈÕ־ij´¦Ôö¼ÓÒ»ÌõÈÕÖ¾¡»£»¶øÊý¾ÝдÅ̾͸ü¸´ÔÓÁË£¬ÒòΪҪÓáºÄܹ»¿ìËÙ¶ÁÈ¡µÄ·½Ê½Ð´ÈëÊý¾Ý¡»¡£

STEAL ºÍ FORCE ²ßÂÔ

³öÓÚÐÔÄÜ·½ÃæµÄÔ­Òò£¬µÚ 5 ²½ÓпÉÄÜÔÚÌá½»Ö®ºóÍê³É£¬ÒòΪһµ©·¢Éú±ÀÀ££¬»¹ÓпÉÄÜÓÃREDOÈÕÖ¾»Ö¸´ÊÂÎñ¡£Õâ½Ð×ö NO-FORCE²ßÂÔ¡£

Êý¾Ý¿â¿ÉÒÔÑ¡ÔñFORCE²ßÂÔ£¨±ÈÈçµÚ 5 ²½ÔÚÌύ֮ǰ±ØÐëÍê³É£©À´½µµÍ»Ö¸´Ê±µÄ¸ºÔØ¡£

ÁíÒ»¸öÎÊÌâÊÇ£¬ÒªÑ¡ÔñÊý¾ÝÊÇÒ»²½²½µÄдÈ루STEAL²ßÂÔ£©£¬»¹ÊÇ»º³å¹ÜÀíÆ÷ÐèÒªµÈ´ýÌá½»ÃüÁîÀ´Ò»´ÎÐÔÈ«²¿Ð´È루NO-STEAL²ßÂÔ£©¡£Ñ¡ÔñSTEAL»¹ÊÇNO-STEALÈ¡¾öÓÚÄãÏëҪʲô£º¿ìËÙдÈ뵫ÊÇ´Ó UNDO ÈÕÖ¾»Ö¸´»ºÂý£¬»¹ÊÇ¿ìËÙ»Ö¸´¡£

×ܽáÒ»ÏÂÕâЩ²ßÂÔ¶Ô»Ö¸´µÄÓ°Ï죺

STEAL/NO-FORCE ÐèÒª UNDO ºÍ REDO: ÐÔÄܸߣ¬µ«ÊÇÈÕÖ¾ºÍ»Ö¸´¹ý³Ì¸ü¸´ÔÓ (±ÈÈç ARIES)¡£¶àÊýÊý¾Ý¿âÑ¡ÔñÕâ¸ö²ßÂÔ¡£ ×¢£ºÕâÊÇÎÒ´Ó¶à¸öѧÊõÂÛÎĺͽ̳ÌÀï¿´µ½µÄ£¬µ«²¢Ã»Óп´µ½¹Ù·½ÎĵµÀïÏÔʽ˵Ã÷ÕâÒ»µã¡£

STEAL/ FORCE Ö»ÐèÒª UNDO.

NO-STEAL/NO-FORCE Ö»ÐèÒª REDO.

NO-STEAL/FORCE ʲôҲ²»ÐèÒª: ÐÔÄÜ×î²î£¬¶øÇÒÐèÒª¾Þ´óµÄÄÚ´æ¡£

¹ØÓÚ»Ö¸´

Ok£¬ÓÐÁ˲»´íµÄÈÕÖ¾£¬ÎÒÃÇÀ´ÓÃÓÃËüÃÇ£¡

¼ÙÉèÐÂÀ´µÄʵϰÉúÈÃÊý¾Ý¿â±ÀÀ£ÁË£¨Ê×Òª¹æ¾Ø£ºÓÀÔ¶ÊÇʵϰÉúµÄ´í¡££©£¬ÄãÖØÆôÁËÊý¾Ý¿â£¬»Ö¸´¹ý³Ì¿ªÊ¼ÁË¡£

ARIES´Ó±ÀÀ£Öлָ´ÓÐÈý¸ö½×¶Î£º

1) ·ÖÎö½×¶Î£º»Ö¸´½ø³Ì¶Áȡȫ²¿ÊÂÎñÈÕÖ¾£¬À´Öؽ¨±ÀÀ£¹ý³ÌÖÐËù·¢ÉúÊÂÇéµÄʱ¼äÏߣ¬¾ö¶¨ÄĸöÊÂÎñÒª»Ø¹ö£¨ËùÓÐδÌá½»µÄÊÂÎñ¶¼Òª»Ø¹ö£©¡¢±ÀÀ£Ê±ÄÄЩÊý¾ÝÐèҪдÅÌ¡£

2) Redo½×¶Î£ºÕâÒ»¹Ø´Ó·ÖÎöÖÐÑ¡ÖеÄÒ»ÌõÈÕÖ¾¼Ç¼¿ªÊ¼£¬Ê¹Óà REDO À´½«Êý¾Ý¿â»Ö¸´µ½±ÀÀ£Ö®Ç°µÄ״̬¡£

ÔÚREDO½×¶Î£¬REDOÈÕÖ¾°´ÕÕʱ¼ä˳Ðò´¦Àí£¨Ê¹ÓÃLSN£©¡£

¶ÔÿһÌõÈÕÖ¾£¬»Ö¸´½ø³ÌÐèÒª¶ÁÈ¡°üº¬Êý¾ÝµÄ´ÅÅÌÒ³LSN¡£

Èç¹ûLSN£¨´ÅÅÌÒ³£©>= LSN£¨ÈÕÖ¾¼Ç¼£©£¬ËµÃ÷Êý¾ÝÒѾ­ÔÚ±ÀÀ£Ç°Ð´µ½´ÅÅÌ£¨µ«ÊÇÖµÒѾ­±»ÈÕÖ¾Ö®ºó¡¢±ÀÀ£Ö®Ç°µÄij¸ö²Ù×÷¸²¸Ç£©£¬ËùÒÔ²»ÐèÒª×öʲô¡£

Èç¹ûLSN£¨´ÅÅÌÒ³£©< LSN£¨ÈÕÖ¾¼Ç¼£©£¬ÄÇô´ÅÅÌÉϵÄÒ³½«±»¸üС£

¼´Ê¹½«±»»Ø¹öµÄÊÂÎñ£¬REDOÒ²ÊÇÒª×öµÄ£¬ÒòΪÕâÑù¼ò»¯Á˻ָ´¹ý³Ì£¨µ«ÊÇÎÒÏàÐÅÏÖ´úÊý¾Ý¿â²»»áÕâô×öµÄ£©¡£

3) Undo½×¶Î£ºÕâÒ»½×¶Î»Ø¹öËùÓбÀÀ£Ê±Î´Íê³ÉµÄÊÂÎñ¡£»Ø¹ö´Óÿ¸öÊÂÎñµÄ×îºóÒ»ÌõÈÕÖ¾¿ªÊ¼£¬²¢ÇÒ°´ÕÕʱ¼äµ¹Ðò´¦ÀíUNDOÈÕÖ¾£¨Ê¹ÓÃÈÕÖ¾¼Ç¼µÄPrevLSN£©¡£

»Ö¸´¹ý³ÌÖУ¬ÊÂÎñÈÕÖ¾±ØÐëÁôÒâ»Ö¸´¹ý³ÌµÄ²Ù×÷£¬ÒÔ±ãдÈë´ÅÅ̵ÄÊý¾ÝÓëÊÂÎñÈÕÖ¾ÏàÒ»Ö¡£Ò»¸ö½â¾ö°ì·¨ÊÇÒÆ³ý±»È¡ÏûµÄÊÂÎñ²úÉúµÄÈÕÖ¾¼Ç¼£¬µ«ÊÇÕâ¸öÌ«À§ÄÑÁË¡£Ïà·´£¬ARIESÔÚÊÂÎñÈÕÖ¾ÖмǼ²¹³¥ÈÕÖ¾£¬À´Âß¼­ÉÏɾ³ý±»È¡ÏûµÄÊÂÎñµÄÈÕÖ¾¼Ç¼¡£

µ±ÊÂÎñ±»¡ºÊÖ¹¤¡»È¡Ïû£¬»òÕß±»Ëø¹ÜÀíÆ÷È¡Ïû£¨ÎªÁËÏû³ýËÀËø£©£¬»ò½ö½öÒòÎªÍøÂç¹ÊÕ϶øÈ¡Ïû£¬ÄÇô·ÖÎö½×¶Î¾Í²»ÐèÒªÁË¡£¶ÔÓÚÄÄЩÐèÒª REDO ÄÄЩÐèÒª UNDO µÄÐÅÏ¢ÔÚ 2 ¸öÄÚ´æ±íÖУº

ÊÂÎñ±í£¨±£´æµ±Ç°ËùÓÐÊÂÎñµÄ״̬£©

ÔàÒ³±í£¨±£´æÄÄЩÊý¾ÝÐèҪдÈë´ÅÅÌ£©

µ±ÐµÄÊÂÎñ²úÉúʱ£¬ÕâÁ½¸ö±íÓÉ»º´æ¹ÜÀíÆ÷ºÍÊÂÎñ¹ÜÀíÆ÷¸üС£ÒòΪÊÇÔÚÄÚ´æÖУ¬µ±Êý¾Ý¿â±ÀÀ£Ê±ËüÃÇÒ²±»ÆÆ»µµôÁË¡£

·ÖÎö½×¶ÎµÄÈÎÎñ¾ÍÊÇÔÚ±ÀÀ£Ö®ºó£¬ÓÃÊÂÎñÈÕÖ¾ÖеÄÐÅÏ¢ÖØ½¨ÉÏÊöµÄÁ½¸ö±í¡£ÎªÁ˼ӿì·ÖÎö½×¶Î£¬ARIESÌá³öÁËÒ»¸ö¸ÅÄ¼ì²éµã£¨check point£©£¬¾ÍÊDz»Ê±µØ°ÑÊÂÎñ±íºÍÔàÒ³±íµÄÄÚÈÝ£¬»¹ÓдËʱ×îºóÒ»ÌõLSNдÈë´ÅÅÌ¡£ÄÇôÔÚ·ÖÎö½×¶Îµ±ÖУ¬Ö»ÐèÒª·ÖÎöÕâ¸öLSNÖ®ºóµÄÈÕÖ¾¼´¿É¡£

½áÓï

дÕâÆªÎÄÕÂ֮ǰ£¬ÎÒÖªµÀÕâ¸öÌâÄ¿Óжà´ó£¬Ò²ÖªµÀдÕâÑùһƪÉîÈëµÄÎÄÕ»áÏ൱ºÄʱ¡£×îºóÖ¤Ã÷ÎÒ¹ýÓÚÀÖ¹ÛÁË£¬Êµ¼ÊÉÏ»¨ÁËÁ½±¶ÓÚÔ¤ÆÚµÄʱ¼ä£¬µ«ÊÇÎÒѧµ½Á˺ܶࡣ

Èç¹ûÄãÏëºÜºÃµØÁ˽âÊý¾Ý¿â£¬ÎÒÍÆ¼öÕâÆªÑо¿ÂÛÎÄ£º¡¶Êý¾Ý¿âϵͳ¼Ü¹¹¡·£¬¶ÔÊý¾Ý¿âÓкܺõĽéÉÜ£¨¹²110Ò³£©£¬¶øÇҷǼÆËã»úרҵÈËʿҲÄܶÁ¶®¡£ÕâÆªÂÛÎijöÉ«µÄ°ïÖúÎÒÖÆ¶¨Á˱¾ÎĵÄд×÷¼Æ»®£¬ËüûÓÐÏñ±¾ÎÄÄÇÑùרעÓÚÊý¾Ý½á¹¹ºÍËã·¨£¬¸ü¶àµÄ½²Á˼ܹ¹·½ÃæµÄ¸ÅÄî¡£

Èç¹ûÄã×ÐϸÔĶÁÁ˱¾ÎÄ£¬ÄãÏÖÔÚÓ¦¸ÃÁ˽âÒ»¸öÊý¾Ý¿âÊǶàôµÄÇ¿´óÁË¡£¼øÓÚÎÄÕºܳ¤£¬ÈÃÎÒÀ´ÌáÐÑÄãÎÒÃǶ¼Ñ§µ½ÁËʲô£º

B+Ê÷Ë÷Òý¸ÅÊö

Êý¾Ý¿âµÄÈ«¾Ö¸ÅÊö

»ùÓڳɱ¾µÄÓÅ»¯¸ÅÊö£¬ÌرðרעÁËÁª½ÓÔËËã

»º³å³Ø¹ÜÀí¸ÅÊö

ÊÂÎñ¹ÜÀí¸ÅÊö

µ«ÊÇ£¬Êý¾Ý¿â°üº¬Á˸ü¶àµÄ´ÏÃ÷Çɼ¼¡£±ÈÈ磬ÎÒ²¢Ã»ÓÐ̸µ½ÏÂÃæÕâЩ¼¬ÊÖµÄÎÊÌ⣺

ÈçºÎ¹ÜÀíÊý¾Ý¿â¼¯ÈººÍÈ«¾ÖÊÂÎñ

ÈçºÎÔÚÊý¾Ý¿âÔËÐеÄʱºò²úÉú¿ìÕÕ

ÈçºÎ¸ßЧµØ´æ´¢£¨ºÍѹËõ£©Êý¾Ý

ÈçºÎ¹ÜÀíÄÚ´æ

ËùÒÔ£¬µ±Äã²»µÃ²»ÔÚÎÊÌâ¶à¶àµÄ NoSQLÊý¾Ý¿âºÍ¼áÈçÅÍʯµÄ¹ØÏµÐÍÊý¾Ý¿âÖ®¼ä¾ñÔñµÄʱºò£¬ÒªÈý˼¶øÐС£²»ÒªÎó»á£¬Ä³Ð© NoSQLÊý¾Ý¿âÊǺܰôµÄ£¬µ«ÊÇËüÃDZϾ¹»¹ÄêÇᣬֻÊǽâ¾öÁËÉÙÁ¿Ó¦ÓùØ×¢µÄÒ»Ð©ÌØ¶¨ÎÊÌâ¡£

Ïà¹ØÎÄÕÂ

»ùÓÚEAµÄÊý¾Ý¿â½¨Ä£
Êý¾ÝÁ÷½¨Ä££¨EAÖ¸ÄÏ£©
¡°Êý¾Ýºþ¡±£º¸ÅÄî¡¢ÌØÕ÷¡¢¼Ü¹¹Óë°¸Àý
ÔÚÏßÉ̳ÇÊý¾Ý¿âϵͳÉè¼Æ ˼·+Ч¹û
 
Ïà¹ØÎĵµ

GreenplumÊý¾Ý¿â»ù´¡Åàѵ
MySQL5.1ÐÔÄÜÓÅ»¯·½°¸
ijµçÉÌÊý¾ÝÖÐ̨¼Ü¹¹Êµ¼ù
MySQL¸ßÀ©Õ¹¼Ü¹¹Éè¼Æ
Ïà¹Ø¿Î³Ì

Êý¾ÝÖÎÀí¡¢Êý¾Ý¼Ü¹¹¼°Êý¾Ý±ê×¼
MongoDBʵս¿Î³Ì
²¢·¢¡¢´óÈÝÁ¿¡¢¸ßÐÔÄÜÊý¾Ý¿âÉè¼ÆÓëÓÅ»¯
PostgreSQLÊý¾Ý¿âʵսÅàѵ
   
6007 ´Îä¯ÀÀ       27