ÒýÑÔ
´«Í³µÄÊý¾Ý¿â¹ÜÀíϵͳ°ÑËùÓÐÊý¾Ý¶¼·ÅÔÚ´ÅÅÌÉϽøÐйÜÀí£¬ËùÒÔ³Æ×÷´ÅÅÌÊý¾Ý¿â£¨DRDB:
Disk-Resident Database£©¡£´ÅÅÌÊý¾Ý¿âÐèҪƵ·±µØ·ÃÎÊ´ÅÅÌÀ´½øÐÐÊý¾ÝµÄ²Ù×÷£¬´ÅÅ̵ĶÁдËÙ¶ÈԶԶСÓÚCPU´¦ÀíÊý¾ÝµÄËÙ¶È£¬ËùÒÔ´ÅÅÌÊý¾Ý¿âµÄÆ¿¾±³öÏÖÔÚ´ÅÅ̶ÁдÉÏ¡£
»ùÓÚ´Ë£¬ÄÚ´æÊý¾Ý¿âµÄ¸ÅÄî±»Ìá³öÀ´ÁË¡£ÄÚ´æÊý¾Ý¿â(MMDB:Main Memory
Database£¬Ò²½ÐÖ÷´æÊý¾Ý¿â)[1]£¬¾ÍÊǽ«Êý¾ÝÈ«²¿»òÕߴ󲿷ַÅÔÚÄÚ´æÖнøÐвÙ×÷µÄÊý¾Ý¿â¹ÜÀíϵͳ£¬¶Ô²éѯ´¦Àí¡¢²¢·¢¿ØÖÆÓë»Ö¸´µÄËã·¨ºÍÊý¾Ý½á¹¹½øÐÐÖØÐÂÉè¼Æ£¬ÒÔ¸üÓÐЧµØÊ¹ÓÃCPUÖÜÆÚºÍÄÚ´æ¡£Ïà¶ÔÓÚ´ÅÅÌ£¬ÄÚ´æµÄÊý¾Ý¶ÁдËÙ¶ÈÒª¸ß³ö¼¸¸öÊýÁ¿¼¶£¬½«Êý¾Ý±£´æÔÚÄÚ´æÖÐÏà±È´Ó´ÅÅÌÉÏ·ÃÎÊÄܹ»¼«´óµØÌá¸ßÓ¦ÓõÄÐÔÄÜ¡£
½üÊ®¼¸ÄêÀ´£¬ÄÚ´æµÄ·¢Õ¹Ò»Ö±×ñÑĦ¶û¶¨ÂÉ[2]£¬ÄÚ´æµÄ¼Û¸ñһֱϽµ£¬¶øÄÚ´æµÄÈÝÁ¿Ò»Ö±ÔÚÔö¼Ó¡£ÏÖÔÚµÄÖ÷Á÷·þÎñÆ÷£¬¼¸°ÙGB»òÕß¼¸TBµÄÄÚ´æ¶¼ºÜ³£¼û£¬ÄÚ´æµÄ·¢Õ¹Ê¹µÃÄÚ´æÊý¾Ý¿âµÃÒÔʵÏÖ¡£
ÓÉÓÚÄÚ´æÊý¾Ý¿âÓ봫ͳµÄ´ÅÅÌÊý¾Ý¿âÔÚÉè¼ÆºÍ¼Ü¹¹É϶¼´ó²»Ïàͬ£¬ËùÒÔ´«Í³µÄÊý¾Ý¿âË÷Òý²»ÊÊÓÃÓÚÄÚ´æÊý¾Ý¿â¡£Ñо¿ÕßΪ¸Ä½øÄÚ´æÊý¾Ý¿âµÄË÷Òý½á¹¹×öÁËÏ൱¶àµÄÑо¿¸ú¹¤×÷¡£ÆäÖУ¬Ó°Ïì½Ï´óµÄË÷ÒýÓÐÔçÆÚµÄTÊ÷¡¢»ùÓÚ»º´æÃô¸Ð(cacheconscious)µÄCSS/CSB+Ê÷£¬Trie-treeºÍHashµÈµÈ¡£±¾ÎľÍÕ⼸ÖÖÓдú±íÐÔµÄË÷ÒýËã·¨½øÐÐÑо¿ºÍ·ÖÎö£¬Îª½øÒ»²½¸Ä½øÄÚ´æÊý¾Ý¿âË÷ÒýËã·¨ºÍÌá¸ßË÷ÒýÐÔÄÜ´òϼáʵµÄ»ù´¡¡£
2¡¢T-tree
2.1 T-tree
T-treeÊÇÕë¶ÔÖ÷´æ·ÃÎÊÓÅ»¯µÄË÷Òý¼¼Êõ[3]¡£T-treeÊÇÒ»ÖÖÒ»¸ö½ÚµãÖаüº¬¶à¸öË÷ÒýÌõÄ¿µÄƽºâ¶þ²æÊ÷£¬T-treeµÄË÷ÒýÏîÎÞÂÛÊÇ´Ó´óС»¹ÊÇËã·¨É϶¼±ÈB-tree¾«¼òµÃ¶à¡£T-treeµÄËÑË÷Ëã·¨²»·ÖËÑË÷µÄÖµÔÚµ±Ç°µÄ½Úµã»¹ÊÇÔÚÄÚ´æÖÐµÄÆäËûµØ·½£¬Ã¿·ÃÎʵ½Ò»¸öеÄË÷Òý½Úµã£¬Ë÷ÒýµÄ·¶Î§¼õÉÙÒ»°ë¡£

ͼ2-1T-TreeµÄ½áµã
T-treeË÷ÒýÓÃÀ´ÊµÏֹؼü×ֵķ¶Î§²éѯ¡£T-treeÊÇÒ»¿ÃÌØÊâÆ½ºâµÄ¶þ²æÊ÷£¨AVL£©£¬ËüµÄÿ¸ö½Úµã´æ´¢Á˰´¼üÖµÅÅÐòµÄÒ»×鹨¼ü×Ö¡£T-tree³ýÁ˽ϸߵĽڵã¿Õ¼äÕ¼ÓÐÂÊ£¬±éÀúÒ»¿ÃÊ÷µÄ²éÕÒËã·¨ÔÚ¸´Ôӳ̶ȺÍÖ´ÐÐʱ¼äÉÏÒ²Õ¼ÓÐÓÅÊÆ¡£ÏÖÔÚT-tree¼º¾³ÉΪÄÚ´æÊý¾Ý¿âÖÐ×îÖ÷ÒªµÄÒ»ÖÖË÷Òý·½Ê½¡£
T-tree¾ßÓÐÒÔÏÂÌØµã£º1£©×ó×ÓÊ÷ÓëÓÒ×ÓÊ÷Ö®²î²»³¬¹ý1£¬2£©ÔÚÒ»¸ö´æ´¢½Úµã¿ÉÒÔ±£´æ¶à¸ö¼üÖµ£¬ËüµÄ×î×óÓë×îÓÒ¼üÖµ·Ö±ðΪÕâ¸ö½ÚµãµÄ×îСÓë×î´ó¼üÖµ£¬ËüµÄ×ó×ÓÊ÷½ö½ö°üº¬ÄÇЩ¼üֵСÓÚ»òµÈÓÚ×îС¼üÖµµÄÒ»¼Ç¼£¬Í¬ÀíÓÒ×ÓÊ÷Ö»°üÀ¨ÄÇЩ¼üÖµ´óÓÚ»òµÈÓÚ×î´ó¼üÖµµÄ¼Ç¼£¬3£©Í¬Ê±ÓµÓÐ×óÓÒ×ÓÊ÷µÄ½Úµã±»³ÆÎªÄÚ²¿½Úµã£¬Ö»ÓµÓÐÒ»¸ö×ÓÊ÷µÄ½Úµã±»³ÆÎª°ëÒ¶½Úµã£¬Ã»ÓÐ×ÓÊ÷µÄ½Úµã±»³ÆÎªÒ¶×Ó£¬4£©ÎªÁ˱£³Ö¿Õ¼äµÄÀûÓÃÂÊ£¬Ã¿Ò»¸öÄÚ²¿½Úµã¶¼ÐèÒª°üº¬Ò»¸ö×îСÊýÄ¿µÄ¼üÖµ¡£ÓÉ´Ë¿ÉÖªT-treeÊÇÒ»¸öÿ¸ö½áµãº¬Óжà¸ö¹Ø¼ü×ֵį½ºâ¶þ²æÊ÷£¬Ã¿¸ö½ÚµãÄڵĹؼü×ÖÓÐÐòÅÅÁУ¬×ó×ÓÊ÷¶¼Òª±È¸ù½Úµã¹Ø¼ü×ÖС£¬ÓÒ×ÓÊ÷¶¼Òª±È¸ù½Úµã¹Ø¼ü×Ö´ó¡£
ÔÚÉÏÊöT-tree½áµã½á¹¹ÖУ¬°üº¬ÈçÏÂÐÅÏ¢:
(1)balance(ƽºâÒò×Ó)£¬Æä¾ø¶ÔÖµ²»´óÓÚ1£¬balance=ÓÒ×ÓÊ÷¸ß¶È-×ó×ÓÊ÷¸ß¶È£»
(2)Left_child_ptrºÍRight_child_ptr·Ö±ð±íʾµ±Ç°½áµãµÄ×ó×ÓÊ÷ºÍÓÒ×ÓÊ÷Ö¸Õ룻
(3)Max_Item±íʾ½áµãÖÐËùÄÜÈÝÄɵļüÖµµÄ×î´óÊý£»
(4)Key[0]ÖÁK[Max_Item-1]Ϊ½áµãÄÚ´æ·ÅµÄ¹Ø¼ü×Ö£»
(5)nItemÊǵ±Ç°½Úµãʵ¼Ê´æ´¢µÄ¹Ø¼ü×Ö¸öÊý¡£
¶ÔÓÚT-treeÓÐÈçÏÂÌØÕ÷£º
(1)ÓëAVLÊ÷ÏàËÆ£¬T-treeÖÐÈκνáµãµÄ×óÓÒ×ÓÊ÷µÄ¸ß¶ÈÖ®²î×î´óΪ1£»
(2)ÓëAVLÊ÷²»Í¬£¬T-treeµÄ½áµãÖпɴ洢¶à¸ö¼üÖµ£¬²¢ÇÒÕâЩ¼üÖµÅÅÁÐÓÐÐò£»
(3)T-tree½áµãµÄ×ó×ÓÊ÷ÖÐÈÝÄɵļüÖµ²»´óÓڸýáµãÖеÄ×î×ó¼üÖµ£»ÓÒ×ÓÊ÷ÖÐÈÝÄɵļüÖµ²»Ð¡ÓڸýáµãÖеÄ×îÓÒ¼üÖµ£»
(4)ΪÁ˱£Ö¤Ã¿¸ö½áµã¾ßÓнϸߵĿռäÕ¼ÓÃÂÊ£¬Ã¿¸öÄÚ²¿½áµãËù°üº¬µÄ¼üÖµÊýÄ¿±ØÐ벻СÓÚij¸öÖ¸¶¨µÄÖµ£¬Í¨³£Îª(Max_Item-2)(Max_ItemΪ½áµãÖÐ×î´ó¼üֵĿ)¡£
2.2 T-treeË÷ÒýµÄ²Ù×÷
ÓÃT-tree×÷ΪË÷Òý·½Ê½Ö÷ÒªÍê³ÉÈý¸ö¹¤×÷£º²éÕÒ£¬²åÈ룬ɾ³ý¡£ÆäÖвåÈëºÍɾ³ý¶¼ÊÇÒÔ²éÕÒΪ»ù´¡¡£ÏÂÃæ·Ö±ð½éÉÜÈýÖÖ²Ù×÷µÄÁ÷³Ì¡£
2.2.1 ²éÕÒ
T-treeµÄ²éÕÒÀàËÆÓÚ¶þ²æÊ÷£¬²»Í¬Ö®´¦Ö÷ÒªÔÚÓÚÿһ½áµãÉϵıȽϲ»ÊÇÕë¶Ô½áµãÖеĸ÷¸öÔªËØÖµ£¬¶øÊÇÊ×Ïȼì²éËùÒª²éÕÒµÄÄ¿±ê¼üÖµÊÇ·ñ°üº¬ÔÚµ±Ç°½áµãµÄ×î×ó¼üÖµºÍ×îÓÒ¼üÖµËùÈ·¶¨µÄ·¶Î§ÄÚ£¬Èç¹ûÊǵϰ£¬ÔòÔÚµ±Ç°½áµãµÄ¼üÖµÁбíÖÐʹÓöþ·Ö·¨½øÐвéÕÒ£»Èç¹ûÄ¿±ê¼üֵСÓÚµ±Ç°½áµãµÄ×î×ó¼üÖµ£¬ÔòÀàËÆµØËÑË÷µ±Ç°½áµãµÄ×óº¢×Ó½áµã£»Èç¹ûÄ¿±ê¼üÖµ´óÓÚµ±Ç°½áµãµÄ×îÓÒ¼üÖµ£¬ÔòÀàËÆµØËÑË÷µ±Ç°½áµãµÄÓÒº¢×Ó½áµã¡£
2.2.2 ²åÈë
T-treeµÄ²åÈëÊÇÒÔ²éÕÒΪ»ù´¡£¬Ó¦ÓòéÕÒ²Ù×÷¶¨Î»Ä¿±ê¼üÖµ²åÈëλÖ㬲¢¼ÇϲéÕÒ¹ý³ÌËùÓöµ½µÄ×îºó½áµã¡£Èç¹û²éÕҳɹ¦£¬Åжϴ˽áµãÖÐÊÇ·ñÓÐ×ã¹»µÄ´æ´¢¿Õ¼ä¡£Èç¹ûÓУ¬Ôò½«Ä¿±ê¼üÖµ²åÈë½áµãÖУ»·ñÔò½«Ä¿±ê¼üÖµ²åÈë´Ë½áµã£¬È»ºó½«½áµãÖеÄ×î×ó¼üÖµ²åÈëµ½ËüµÄ×ó×ÓÊ÷ÖÐ(´ËʱÊǵݹé²åÈë²Ù×÷)£¬Ö®ºó½áÊø£»·ñÔò·ÖÅäнáµã£¬²¢²åÈëÄ¿±ê¼üÖµ£»È»ºó¸ù¾ÝÄ¿±ê¼üÖµÓë½áµãµÄ×î´ó×îС¼üÖµÖ®¼äµÄ¹ØÏµ£¬½«Ð·ÖÅäµÄ½áµãÁ´½ÓΪ½áµãµÄ×óº¢×Ó»òÓÒº¢×Ó£»¶ÔÊ÷½øÐмì²é£¬ÅжÏT-treeµÄƽºâÒò×ÓÊÇ·ñÂú×ãÌõ¼þ£¬Èç¹ûƽºâÒò×Ó²»Âú×ãÔòÖ´ÐÐÐýת²Ù×÷¡£
2.2.3 ɾ³ý
T-treeµÄɾ³ý²Ù×÷Ò²ÊÇÒÔ²éÕÒΪ»ù´¡£¬Ó¦ÓòéÕÒ²Ù×÷¶¨Î»Ä¿±ê¼üÖµ¡£Èç¹û²éÕÒʧ°Ü£¬Ôò½áÊø£»·ñÔòÁîNΪĿ±ê¼üÖµËùÔڵĽáµã£¬²¢´Ó½áµãNÖÐɾ³ýÄ¿±ê¼üÖµ£»É¾³ý½Úµãºó£¬Èç¹û½áµãNΪ¿Õ£¬Ôòɾ³ý½áµãN£¬²¢¶ÔÊ÷µÄƽºâÒò×Ó½øÐмì²é£¬ÅжÏÊÇ·ñÐèÒªÖ´ÐÐÐýת²Ù×÷£»Èç¹û½áµãNÖеļüÖµÊýÁ¿ÉÙÓÚ×îСֵ£¬Ôò¸ù¾ÝNµÄƽºâÒò×Ó¾ö¶¨´Ó½áµãNµÄ×ó×ÓÊ÷ÖÐÒÆ³ö×î´óµÄ¼üÖµ»òÕßÓÒ×ÓÊ÷ÖÐÒÆ³ö×îСֵÀ´Ìî³ä¡£
2.3 T-treeË÷ÒýʵÏֹؼü¼¼Êõ
ʵÏÖT-treeË÷Òý¼´ÒªÊµÏÖT-treeµÄ²éÕÒ£¬²åÈëºÍɾ³ý¡£ÆäÖÐÓÖÒÔ²éÕÒΪ»ù´¡£¬¶ÔT-treeµÄά»¤Ò²¾ÍÊÇT-treeµÄÐýתΪ¹Ø¼ü¡£µ±ÓÉÓÚ²åÈë»òɾ³ý¼üÖµµ¼ÖÂÊ÷µÄʧºâ£¬ÔòÒª½øÐÐT-treeµÄÐýת¡£Ê¹Ö®ÖØÐ´ﵽƽºâ¡£
ÔÚ²åÈëÇé¿öÏ£¬ÐèÒªÒÀ´Î¶ÔËùÓÐÑØ×Å´Óд´½¨½áµãµ½¸ù½áµã·¾¶ÖеĽáµã½øÐмì²é£¬Ö±µ½³öÏÖÈçÏÂÁ½ÖÖÇé¿ö֮һʱÖÐÖ¹£ºÄ³¸ö±»¼ì²é½áµãµÄÁ½¸ö×ÓÊ÷¸ß¶ÈÏàµÈ£¬´Ëʱ²»ÐèÒªÖ´ÐÐÐýת²Ù×÷£»Ä³¸ö±»¼ì²é½áµãµÄÁ½¸ö×ÓÊ÷µÄ¸ß¶ÈÖ®²î´óÓÚ1£¬´Ëʱ¶Ô¸Ã½áµã½öÐèÖ´ÐÐÒ»´ÎÐýת²Ù×÷¼´¿É¡£
ÔÚɾ³ýÇé¿öÏ£¬ÀàËÆµØÐèÒªÒÀ´Î¶ÔËùÓÐÑØ×Å´Ó´ýɾ³ý½áµãµÄ¸¸½áµãµ½¸ù½áµã·¾¶ÖеĽáµã½øÐмì²é£¬ÔÚ¼ì²é¹ý³ÌÖе±·¢ÏÖij¸ö½áµãµÄ×óÓÒ×ÓÊ÷¸ß¶ÈÖ®²îÔ½½çʱ£¬ÐèÒªÖ´ÐÐÒ»´ÎÐýת²Ù×÷¡£Óë²åÈë²Ù×÷²»Í¬µÄÊÇ£¬Ö´ÐÐÍêÐýת²Ù×÷Ö®ºó£¬¼ì²é¹ý³Ì²»ÄÜÖÐÖ¹£¬¶øÊDZØÐëÒ»Ö±Ö´Ðе½¼ì²éÍê¸ù½áµã¡£
ÓÉ´Ë¿ÉÒÔ¿´³ö£¬¶ÔÓÚ²åÈë²Ù×÷£¬×î¶àÖ»ÐèÒªÒ»´ÎÐýת²Ù×÷¼´¿ÉʹT-tree»Ö¸´µ½Æ½ºâ״̬£»¶ø¶ÔÓÚɾ³ý²Ù×÷Ôò¿ÉÄÜ»áÒýÆðÏòÉϵÄÁ¬Ëø·´Ó¦£¬Ê¹¸ß²ã½áµã·¢ÉúÐýת£¬Òò¶ø¿ÉÄÜÐèÒª½øÐжà´ÎÐýת²Ù×÷¡£
ΪÁ˶ÔT-tree½øÐÐÆ½ºâ£¬ÐèÒª½øÐÐÐýת²Ù×÷£¬ÐýתÊÇT-treeÖÐ×î¹Ø¼üÒ²ÊÇ×îÄѵĵIJÙ×÷£¬ÏÂÃæ½éÉÜT-treeÐýתµÄ¼¼Êõ¡£Ðýת¿É·ÖΪËÄÖÖÇé¿ö£ºÓÉ×óº¢×ÓµÄ×ó×ÓÊ÷µÄ²åÈ루»òÕßɾ³ý£©ÒýÆðµÄÐýת¼ÇΪLLÐýת£¬ÀàËÆÓÐLR£¬RR¼°RLÐýת¡£²åÈëʱµÄÇé¿öÓëɾ³ýÀàËÆ¡£
3¡¢CSS/CSB+Ê÷
3.1 CSS-trees
3.1.1 Introduction
CSS-trees(Cache-SensitiveSearch Trees),¿ÉÒÔÌṩ±È¶þ·Ö²éÕÒ¸üΪѸËٵIJéѯ²Ù×÷¶øÓÖ²»Ðè´óÁ¿¶îÍâµÄ¿Õ¼ä[4]¡£¸Ã¼¼ÊõÔÚÔÚÒ»¸öÒÔÅźÃÐòµÄÊý×é¶¥¶Ë´æ´¢Ò»¸öĿ¼½á¹¹£¬ÇÒ¸ÃĿ¼½á¹¹µÄ½Úµã´óСÓë»úÆ÷cache-line´óСÏàÆ¥Åä¡£½«¸ÃĿ¼½á¹¹´æ´¢ÔÚÊý×éÖжøÎÞÐè´æ´¢ÄÚ²¿½ÚµãµÄÖ¸Õ룬×Ó½Úµã¿Éͨ¹ýÊý×éÆ«ÒÆÁ¿¶¨Î»£¬ÕâÓëB+-trees²»Í¬¡£
3.2 FULL CSS-Tree
¹¹ÔìÒ»¿Ã½áµã°üº¬m¸ö¼üÖµµÄ²éѯÊ÷£¬Ê÷µÄÉî¶ÈÊÇd£¬ÄÇôһֱµ½d-1µÄÉî¶ÈÕâ¿ÃÊ÷ÊÇÒ»¿ÃÍêÈ«(m+1)-²éѯÊ÷£¬¶øÔÚd²ãÒ¶×Ó½áµã´Ó×óÍùÓÒ·Ö²¼¡£Ò»¿Ãm=4µÄʵÀýÊ÷ͼ3-1Ëùʾ£¬ÆäÖз½¿éÊý¾ÍÊǽáµãÊý£¬ÇÒÿ¸ö½áµãÓÐËĸö¼üÖµ¡£

CSS-TreeµÄ½áµã¿ÉÒÔ´æ´¢ÔÚÊý×éÖУ¬Èçͼ3-2Ëùʾ£º

3.2.1 ¹¹ÔìFULL CSS-Tree
½«Ò»¸öÒÑÅźÃÐòµÄÊý×é¹¹ÔìÒ»¿ÃÏàÓ¦µÄFull CSS-Tree£¬Ê×ÏȽ«Êý×é·ÖΪÁ½²¿·Ö£¬²¢ÇÒÔÚÒ¶×Ó½ÚµãºÍÊý×éÔªËØ¼ä½¨Á¢Æ¥Å䡣Ȼºó´Ó×îºóÒ»¸öÄÚ²¿½Úµã¿ªÊ¼£¬½«½ÚµãÖ±½Ó×ó×ÓÊ÷µÄ×î´ó¼üÖµ×÷Ϊ½ÚµãÈë¿Ú¡£¶ÔÓÚijһЩÄÚ²¿½Úµã£¬Ò²¾ÍÊÇ×îÉî²ã×îºóÒ»¸öÒ¶×Ó½ÚµãµÄ׿ÏÈ£¬¿ÉÄÜÍêÈ«¼üÖµ£¬¿ÉÒÔÓÃÊý×éǰ°ë²¿·Ö×îºóµÄÒ»¸öÔªËØÀ´Ìî³äÕâЩ¼üÖµ£¬ËùÒÔÔÚijЩÄÚ²¿½Úµã»áÓÐһЩ¸´ÖƵļüÖµ¡£¾¡¹ÜÒªÔöÁ¿¸üÐÂÒ»¿ÃFull
CSS-TreeÊ÷ÊǺÜÀ§Äѵ쬵«¹¹ÔìÕâÑùÒ»¿ÃÊ÷»¨·Ñ²¢²»´ó¡£ÊµÑé±íÃ÷¶ÔÓÚÓÐ×ÅÁ½Ç§Îå°ÙÍò¼üÖµµÄÊý×飬¹¹ÔìÆäÏàÓ¦µÄFull
CSS-Tree»¨·ÑµÄʱ¼ä²»×ãÒ»Ãë¡£
3.2.2 ²éѯFull CSS-Tree
´Ó¸ù½Úµã¿ªÊ¼£¬Ã¿´Î¶¼²éѯһ¸öÄÚ²¿½Úµã£¬ÀûÓöþ·Ö²éÕÒÀ´¾ö¶¨²éÕÒÄÄÒ»¸ö·ÖÖ§£¬Öظ´ÉÏÊöÐÐΪֱµ½Ò¶×ӽڵ㣬×îºó½«Ò¶×Ó½ÚµãÓëÅźÃÐòµÄÊý×é½øÐÐÆ¥Åä¡£
ÔÚ½ÚµãÄÚËùÓеIJéѯ¶¼ÓÉif-else¹¹³É£¬ÔÚÄÚ²¿½Úµã½øÐжþ·Ö²éÕÒʱ£¬Ò»Ö±±È½Ï×ó±ßµÄ¼üÖµÊÇ·ñ²»Ð¡ÓÚÒª²éѯµÄ¼üÖµ£¬µ±ÕÒµ½µÚÒ»¸ö±ÈÒª²éѯµÄ¼üֵСʱ£¬Í£Ö¹±È½Ï²¢½øÈëÓұߵķÖÖ§£¨Èç¹ûÕÒ²»µ½ÕâÑùµÄÖµ£¬¾Í½øÈë×î×ó±ßµÄ·ÖÖ§£©¡£ÕâÑù¿ÉÒÔ±£Ö¤µ±ÔÚ½ÚµãÖÐÓи´ÖƵÄֵʱ£¬ÎÒÃÇ¿ÉÒÔÔÚËùÓи´ÖƵļüÖµÖÐÕÒµ½×î×ó±ßµÄ¼üÖµ¡£
3.3 LevelCSS-Tree
¶ÔÓÚÿ¸ö½ÚµãÓÐm¸ö¼Ç¼µÄFull CSS-Tree£¬ÓÐÑϸñµÄm¸ö¼üÖµ£¬ËùÓеļǼ¶¼»á±»ÀûÓõ½¡£¶ÔÓÚm=2t£¬ÎÒÃǶ¨Òåÿ¸ö½ÚµãÖ»ÓÐÖ»ÓÐm-1Ìõ¼Ç¼£¬²¢ÇÒÓÐÒ»¸ö·ÖÖ§Òò×Óm¡£Ò»¿ÃLevel
CSS-TreeÊ÷±ÈÒ»¿ÃÏàÓ¦µÄFull CSS-TreeÊ÷µÄÉî¶È´ó£¬ÒòΪ·ÖÖ§Òò×ÓÊÇm¶ø²»ÊÇm+1£¬È»ºó¶ÔÓÚÿһ¸ö½Úµã£¬ÐèÒªµÄͬ°éÊý¸üÉÙ¡£ÈôNΪһ¸öÒÑÅźÃÐòµÄÊý×éÔªËØËù¶ÔÓ¦µÄ½ÚµãÊý£¬Level
CSS-TreeÓÐlogmN²ã£¬¶øFull CSS-TreeÓÐlogm+1N²ã¡£Ã¿¸ö½ÚµãµÄͬ°éÊýÊÇt£¬¶øFull
CSS-treeÊÇt*(1+2/(m+1))£¬ËùÒÔLevel CSS-treeµÄ×ܵÄͬ°éÊýÊÇlogmN*t=log2N,¶øFull
CSS-treeÊÇlogm+1N*t*(1+2/(m+1))=log2N*logm+1m*(1+2(m+1)).Òò´Ë£¬Level
CSS-TreeËùÐèµÄcompanionÊý±ÈFull CSS-treeÉÙ¡£ÁíÒ»·½Ã棬Level CSS-TreeÐèÒªlogmN¸öcache
accesses£¬±éÀúlogmN¸ö½Úµã£¬¶øFull CSS-TreeÐèlogm+1N¡£
¹¹½¨Ò»¿ÃLevel CSS-TreeÓëFull CSS-TreeÀàËÆ£¬ÎÒÃÇÒ²¿ÉÒÔÀûÓÃÿ¸ö½ÚµãµÄ¿Õ²Û£¬À´´æ´¢×îºóÒ»¸ö·ÖÖ§µÄ×î´óÖµ£¬À´±ÜÃâ±éÀúÕû¿Ã×ÓÊ÷À´»ñÈ¡×î´óÔªËØÖµ¡£²éѯһ¿ÃLevel
CSS-TreeÒ²Óë²éѯFull CSS-TreeÀàËÆ£¬Î¨Ò»µÄ²»Í¬¾ÍÊÇ×Ó½ÚµãÆ«ÒÆÁ¿µÄ¼ÆËã¡£
3.4 CSB+-Tree
3.4.1 Introduction
¾¡¹ÜCSS-TreeÏà±È¶þ·Ö²éÕÒºÍT-Trees²éѯÐÔÄܸüºÃ£¬µ«ÊÇËüÊÇÓÃÓÚ¾ö²ßÖ§³ÖµÄÓÐ×ÅÏà¶Ô¾²Ì¬Êý¾ÝµÄ¹¤×÷¸ºÔØÉè¼ÆµÄ¡£CSB+-Tree(CacheSensitive
B+-Trees)[4],ÊÇB+-TreesµÄ±äÌ壬Á¬Ðø´æ´¢¸ø¶¨½ÚµãµÄ×ӽڵ㣬²¢ÇÒÖ»´æ´¢½ÚµãµÄµÚÒ»¸ö×Ó½ÚµãµÄµØÖ·£¬ÆäËû×Ó½ÚµãµÄµØÖ·¿ÉÒÔͨ¹ýÏà¶ÔÕâ¸ö×Ó½ÚµãµÄÆ«ÒÆÁ¿¼ÆËã»ñµÃ¡£ÓÉÓÚÖ»´æ´¢Ò»¸ö×Ó½ÚµãµÄÖ¸Õ룬cacheµÄÀûÓÃÂÊÊǺܸߵģ¬ÓëB+-TreeÀàËÆ£¬CSB+-TreeÖ§³ÖÔöÁ¿¸üС£
CSB+-TreeÓÐÁ½ÖÖ±äÌ壬·Ö¶ÎCSB+-Tree(SegmentedCSB+-tree)ºÍÍêÈ«CSB+-tree(FullCSB+-Tree).·Ö¶ÎCSB+-Tree½«×Ó½Úµã·Ö¶Î£¬ÔÚͬһ¶ÎµÄ×Ó½ÚµãÁ¬Ðø´æ´¢£¬ÔÚÿ¸ö½ÚµãÖУ¬Ö»ÓÐÿһ¶ÎµÄÆðʼµØÖ·²Å»á±»´æ´¢¡£µ±ÓзÖÁÑʱ£¬·Ö¶ÎCSB+-Tree¿ÉÒÔ¼õÉÙ¸´ÖÆ¿ªÏú£¬ÒòΪֻÓÐÒ»¸ö·Ö¶ÎÐèÒªÒÆ¶¯¡£ÍêÈ«CSB+-TreeΪÕû¸ö½ÚµãÖØÐ·ÖÅä¿Õ¼ä£¬Òò´Ë¼õÉÙÁË·ÖÁÑ¿ªÏú¡£
3.4.2 CSB+-TreeÉϵIJÙ×÷
1£© Bulkload.
¶ÔÓÚCSB+-TreeÊ÷£¬Ò»¸öÓÐЧµÄbulkload·½·¨¾ÍÊÇÒ»²ãÒ»²ãµÄ½¨Á¢Ë÷Òý½á¹¹¡£ÎªÃ¿Ò»¸öÒ¶½Úµã·ÖÅä¿Õ¼ä£¬¼ÆËãÔڸ߲ãÐèÒªµÄ½ÚµãÊý£¬²¢¸ø¸Ã²ã·ÖÅäÁ¬ÐøµÄ´æ´¢¿Õ¼ä¡£Í¨¹ý½«µÍ²ãÿһ¸ö½ÚµãµÄ×î´óÖµÌîÈë¸ß²ãµÄ½Úµã£¬²¢ÉèÖÃÿһ¸ö¸ß²ã½ÚµãµÄµÚÒ»¸ö×Ó½ÚµãÖ¸Õë¡£ÖØ¸´ÉÏÊö²Ù×÷Ö±µ½¸ß²ãÖ»ÓÐÒ»¸ö½Úµã£¬ÇÒÕâ¸ö½ÚµãΪ¸ù½Úµã¡£ÒòΪͬһ²ãµÄËùÓнڵãÊÇÁ¬ÐøµÄ£¬ËùÒÔ¹¹Ôì½Úµã×éÎÞÐè¶îÍâµÄ¸´ÖƲÙ×÷¡£
2£© Search
²éѯCSB+-TreeÓë²éѯB+-TreeÀàËÆ£¬µ±×îÓұ߽ڵãµÄ¼üÖµK±ÈÒª²éѯµÄ¼üֵС£¬¸øµÚÒ»¸ö×Ó½ÚµãÔö¼ÓKµÄÆ«ÒÆÁ¿À´»ñµÃ×Ó½ÚµãµÄµØÖ·¡£ÀýÈ磬KÊǽڵãµÄµÚÈý¸ö¼üÖµ£¬¿ÉÒÔÓÃÒ»¸öcÓï¾äÕÒµ½×ӽڵ㣺child=first_child+3£¬ÆäÖÐchildºÍfirst_childÊǽڵãµÄÖ¸Õë¡£
3£© Insertion
¶ÔCSB+-TreeµÄ²åÈë²Ù×÷Ò²ÓëB+-TreeÀàËÆ£¬Ê×ÏÈÒª²éÕÒ¼üÖµµÄ²åÈë¿Ú£¬Ò»µ©¶¨Î»ÖÁÏàÓ¦Ò¶½Úµã£¬ÅжϸÃÒ¶½ÚµãÊÇ·ñÓÐ×ã¹»µÄ¿Õ¼ä£¬Èç¹ûÓУ¬¾Í¼òµ¥µÄ½«¼üÖµ·ÅÖÃÔÚ¸ÃÒ¶½ÚµãÖУ¬·ñÔò£¬ÐèÒª·ÖÁѸÃÒ¶½Úµã¡£
µ±ÐèÒª·ÖÁÑÒ¶½Úµãʱ£¬»ùÓÚ¸¸½ÚµãÊÇ·ñÓÐ×ã¹»µÄ¿Õ¼ä´æ·Å¼üÖµ»á²úÉúÁ½ÖÖÇé¿ö¡£¼ÙÉ踸½ÚµãpÓÐ×ã¹»µÄ¿Õ¼ä£¬ÁîfΪpµÄµÚÒ»¸ö×Ó½ÚµãµÄÖ¸Õ룬gΪfÖ¸ÏòµÄ½Úµã×飬¹¹½¨Ò»¸öеıÈg¶àÁËÒ»¸ö½ÚµãµÄ½Úµã×ég¡¯£¬½«gÖÐËùÓÐµÄ½Úµã¸´ÖÆµ½g¡¯£¬gÖÐÒª·ÖÁѵĽڵãÔÚg¡¯ÖбäΪÁ½¸ö½Úµã£¬¸üÐÂpÖеÚÒ»¸ö×Ó½ÚµãµÄÖ¸Õëf£¬Ê¹ËüÖ¸Ïòg¡¯£¬²¢ÇÒÖØÐ·ÖÅäg¡£
µ±¸¸½ÚµãûÓжîÍâµÄ¿Õ¼ä²¢ÇÒ×ÔÉíÐèÒª·ÖÁÑʱ£¬ÎÊÌâÏԵøüΪ¸´ÔÓ¡£ÁîfΪpÖеÚÒ»¸ö½ÚµãµÄÖ¸Õ룬ÐèÒª¹¹½¨ÐµĽڵã×ég¡¯£¬½«gÖеĽڵã¾ù·ÖÖÁg¡¯ºÍgÖУ¬pÖÐÒ»°ëµÄ¼üÖµ×ªÒÆÖÁg¡¯ÖС£ÎªÁ˽«p·ÖÁÑΪpºÍp¡¯£¬°üº¬pµÄ½Úµã×éÐèÒªÏñµÚÒ»ÖÖÇé¿öÒ»Ñù½øÐи´ÖÆ£¬»òÕߣ¬Èç¹û½Úµã×éÒ²ÊÇÂúµÄ£¬ÎÒÃÇÐèÒªµÝ¹éµÄ·ÖÁÑpµÄ¸¸½Úµã¡£¸¸½ÚµãÔÙÖØ¸´ÉÏÊö²Ù×÷¡£
4£©Deletion
ɾ³ý²Ù×÷ÀàËÆÓÚ²åÈë²Ù×÷£¬Ò»°ãµÄ£¬¼òµ¥µÄ¶¨Î»Êý¾ÝÈë¿Ú²¢ÇÒ¼ÓÒÔɾ³ý¡£ÎÞÐèµ÷ÕûÊ÷±£Ö¤50%µÄoccupancy[5]
3.4.3 Segmented CSB+-Tree
¿¼ÂÇ128×Ö½ÚµÄcache-line£¬CSB+-TreeÖÐÿ¸ö½Úµã×î¶àÓÐ30¸ö¼üÖµ£¬Òâζ×Åÿ¸ö½Úµã¿ÉÒÔÓÐ31¸ö×ӽڵ㣬ÄÇôһ¸ö½Úµã×é×î´ó¿É´ï31*128½ü4KB£¬Òò´Ëÿһ¸ö·ÖÁÑ£¬ÐèÒª¸´ÖÆ4KBµÄÊý¾ÝÀ´´´½¨Ò»¸ö½Úµã×飬Èôcache-line¸ü´ó£¬·ÖÁÑÒ»¸ö½ÚµãµÄ¿ªÏú½«»á¸ü´ó¡£
Ð޸Ľڵã½á¹¹¿ÉÒÔ¼õÉÙ·ÖÁÑʱµÄ¸´ÖƲÙ×÷¡£¿ÉÒÔ½«×Ó½Úµã·Ö¶Î£¬½«Ã¿Ò»¶ÎµÄµØÖ·´æ´¢ÔÚ½ÚµãÖУ¬Ã¿Ò»¶ÎÐγÉÁËÒ»¸ö½Úµã×飬ֻÓÐÔÚͬһ¶ÎµÄ×ӽڵ㱻Á¬Ðø´æ´¢¡£µÚÒ»ÖÖ¿¼ÂÇÊǹ̶¨Ã¿Ò»¸ö·Ö¶ÎµÄ´óС£¬Ìî³äµÚÒ»¸ö·Ö¶ÎµÄ½Úµã£¬Ò»µ©µÚÒ»¸ö·Ö¶ÎÂúÁË£¬¾Í½«½Úµã·ÅÔÚµÚ¶þ¸ö·Ö¶Î¡£ÈôÒ»¸ö½ÚµãÂäÔÚµÚ¶þ¸ö·Ö¶Î£¬ÎÒÃÇÖ»Ð轫µÚ¶þ¸ö·Ö¶ÎµÄ½Úµã¸´ÖƵ½ÐµĶÎÖУ¬¶øÎÞÐè¹ÜµÚÒ»¸ö·Ö¶Î£¬ÈôеĽڵãÂäÔÚµÚÒ»¸ö·Ö¶Î(ÒѾÂúÁË)£¬ÎÒÃÇÐèÒª½«Êý¾Ý´ÓµÚÒ»¸ö·Ö¶ÎÒÆÖÁµÚ¶þ¸ö·Ö¶Î£¬ÔÚÉÏÊöÀý×ÓÖУ¬Õë¶ÔËæ»ú²åÈ룬·ÖÁѲúÉúµÄÊý¾Ý¸´Öƽ«»á¼õÉÙÖÁ1/2(1/2+3/4)*4KB=2.5KB.ÁíÒ»ÖÖ¾ÍÊÇÔÊÐíÿ¸ö·Ö¶ÎµÄ´óС²»Í¬£¬×îÖÕ½«½Úµã·ÖΪÁ½¶Î¡£µ±Óнڵã²åÈëʱ£¬ÎªÕâ¸ö½ÚµãËùÊôµÄ·Ö¶Î´´½¨Ò»¸öеķֶΣ¬²¢¸üÐÂÏàÓ¦·Ö¶ÎµÄ´óС¡£ÔÚÕâÖÖ·½·¨ÖУ¬ÑϸñÀ´ËµÃ¿´Î²åÈëֻɿ¼°µ½Ò»¸ö·Ö¶Î(µ«µ±¸¸½ÚµãÒ²ÐèÒª·ÖÁÑ£¬´ËʱÁ½¸ö·Ö¶Î¶¼Òª¸´ÖÆ)£¬ÈôÒ»¸öеĽڵãµÈ¿ÉÄܵÄÂäÈëÆäÖÐÒ»¸ö·Ö¶Î£¬Ò»¸ö·ÖÁѲúÉúµÄÊý¾Ý¸´ÖÆÁ¿Îª1/2*4KB=2KB£¬ÕâÖÖ·½·¨¿ÉÒÔ½øÒ»²½µÄ¼õÉÙÊý¾Ý¸´ÖÆÁ¿¡£ÓÐÁ½¸ö·Ö¶ÎµÄSegmentedCSB+TreeÈçͼ3-3Ëùʾ(ÿ¸öÒ¶½ÚµãÖ»ÓÐÁ½¸ö¼üÖµ)£º

·Ö¶ÎCSB+-Tree¿ÉÖ§³ÖËùÓжÔÊ÷µÄ²Ù×÷£¬·½·¨Óë·Ç·Ö¶ÎCSB+-TreeÀàËÆ£¬È»¶ø£¬²éÕÒÿ¸ö½ÚµãµÄÓÒº¢×Ó±ÈÆð·Ç·Ö¶ÎµÄCSB+-TreeµÄ¿ªÏú´ó£¬ÒòΪÐèÒªÕÒµ½º¢×ÓËùÔڵķֶΡ£
3.4.4 FULLCSB+-Tree
ÔÚFULLCSB+-TreeÖУ¬½Úµã·ÖÁѵĿªÏú±ÈCSB+-TreeС¡£ÔÚCSB+-TreeÖУ¬µ±½Úµã·ÖÁÑʱ£¬ÐèÒª½«½Úµã×éÕû¸ö¸´ÖƵ½ÐµÄ×éÖУ¬¶øÔÚFullCSB+-TreeÖУ¬Ö»Ðè·ÃÎʽڵã×éµÄÒ»°ë¡£¶ÔÓÚÕâÖÖ×ªÒÆ²Ù×÷µÄÔ´µØÖ·ºÍÄ¿µÄµØÖ·ÓдóµÄ½»²æ£¬·ÃÎʵÄcache-lineµÄÊýÄ¿ÏÞÖÆÔÚsÄÚ¡£FULLCSB+-TreeÔÚ·ÖÁÑÉÏµÄÆ½¾ùʱ¼ä¿ªÏúÊÇ0.5s£¬¶øCSB+-TreeÐèʱ2s¡£
3.5 ʱ¼ä¿Õ¼ä·ÖÎö
¼Ù¶¨¼üÖµ¡¢×Ó½ÚµãÖ¸Õë¡¢Ôª×éIDÓÐ×ÅÏàͬµÄ¿Õ¼ä´óСK£¬nΪҶ½ÚµãÊý£¬cΪcache-lineµÄ×Ö½ÚÊý£¬tΪ·Ö¶ÎCSB+-TreeµÄ·Ö¶ÎÊý¡£Ã¿¸ö½ÚµãµÄ²ÛֵΪm£¬ÆäÖÐm=c/K£¬¼Ù¶¨½Úµã´óСÓëcache-lineÏàͬ£¬¸÷¸ö²ÎÊý¼°ÆäÏàÓ¦µÄÖµÈçͼ3-4Ëùʾ£º

ͼ3-5ÏÔʾÁ˸÷ÖÖ·½·¨¼ä·ÖÖ§Òò×Ó¡¢¼üÖµ²îÒìÊý¡¢cacheδÃüÖÐÊý¡¢Ã¿¸ö½ÚµãÆäËû²îÒìµÄ±È½Ï¡£B+-TreeµÄ·ÖÖ§Òò×Ó±ÈCSS-TreeС£¬¶øCSB+-Tree´æ´¢µÄ×Ó½ÚµãÖ¸ÕëÉÙ£¬ËùÐèµÄ·ÖÖ§Òò×ÓÓëCSS-TreeÏà½ü¡£Õâµ¼ÖÂÿ¸ö·½·¨µÄcacheδÃüÖдÎÊý²»Ò»Ñù¡£½ÚµãµÄ·ÖÖ§Òò×ÓÔ½´ó£¬cacheδÃüÖдÎÊýÏàÓ¦µÄԽС¡£ÔÚCSB+-TreeÿÔö¼ÓÒ»¸ö·Ö¶Î£¬·ÖÖ§Òò×Ӿͻá¼õÉÙ2£¬ÕâÊÇÓÉÓÚÐèÒªÒ»¸ö²ÛÀ´´æ´¢×Ó½ÚµãÖ¸Õ룬ÁíÒ»¸ö²ÛÀ´´æ´¢ÐÂÔö·Ö¶ÎµÄ´óС¡£Ò»°ã¶øÑÔ£¬B+-TreeÖнڵãµÄ70%¿Õ¼äÊÇÂúµÄ£¬ÐèÒªÏàÓ¦µÄµ÷Õû·ÖÖ§Òò×Ó´óС¡£[6]

ͼ 3-5 CSB+-Tree²éѯʱ¼ä·ÖÎö
ͼ3-6ÏÔʾÁËÔÚ·ÖÁÑʱԤÆÚÒª·ÃÎʵÄcache-lineÊý¡£ÓÉÓÚ¸´ÖÆÊ±Ô´µØÖ·ºÍÄ¿µÄµØÖ·Óн»²æ£¬ËùÒÔFullCSB+-TreeËùÐèµÄÊýĿС¡£·ÖÁÑ¿ªÏúÊDzåÈë²Ù×÷×Ü¿ªÏúµÄÒ»²¿·Ö£¬ÁíÒ»²¿·ÖÊǶ¨Î»ÓÅÒ¶×Ó½Úµã²úÉúµÄ²éѯ¿ªÏú¡£·ÖÁÑ¿ªÏúÏà¶Ô¶ÀÁ¢ÓÚÊ÷µÄÉî¶È£¬ÕâÊÇÓÉÓÚ´ó¶àÊýµÄ·ÖÁѶ¼·¢ÉúÔÚÒ¶½Úµã¡£È»¶ø£¬µ±Ê÷µÄ¹æÄ£Ô½À´Ô½´óʱ£¬ÏàÓ¦µÄ²éѯ²úÉúµÄ¿ªÏúÒ²»áÔö´ó¡£CSB+-TreeµÄ·ÖÁÑ¿ªÏú±ÈB+-Tree´ó£¬µ«ÊDzåÈë²úÉúµÄ×Ü¿ªÏú»¹ÓëÊ÷µÄ¹æÄ£Óйء£

ͼ3-7 ÏÔʾÁ˲»Í¬Ëã·¨µÄ¿Õ¼äÐèÇó¡£¼Ù¶¨ËùÓнڵã70%µÄ¿Õ¼äÊÇÂúµÄ[6]£¬ÇÒ·Ö±ð¼ÆËãÄÚ²¿½ÚµãºÍÒ¶½ÚµãµÄ¿Õ¼ä´óС£¬¼Ù¶¨Ã¿¸öÒ¶½ÚµãÓÐ2¸öÐֵܽڵãÖ¸Õë¡£ÄÚ²¿½Úµã¿Õ¼ä´óСµÈÓÚÒ¶½Úµã¿Õ¼ä³ËÒÔ1/(q-1)(qΪ·ÖÖ§Òò×Ó),ÕâÀï²»±È½ÏCSS-Tree£¬ÒòΪCSS-Tree²»¿ÉÄܲ¿·ÖÂú¡£

4 Trie-treeË÷Òý
4.1 Trie-tree
Trie-Tree[7]ÓֳƵ¥´Ê²éÕÒÊ÷»ò¼üÊ÷£¬ÊÇÒ»ÖÖÊ÷Ðνṹ£¬ÊÇÒ»ÖÖ¹þÏ£Ê÷µÄ±äÖÖ¡£µäÐÍÓ¦ÓÃÊÇÓÃÓÚͳ¼ÆºÍÅÅÐò´óÁ¿µÄ×Ö·û´®£¨µ«²»½öÏÞÓÚ×Ö·û´®£©£¬ËùÒÔ¾³£±»ËÑË÷ÒýÇæÏµÍ³ÓÃÓÚÎı¾´ÊƵͳ¼Æ¡£ËüµÄÓŵãÊÇ£º×î´óÏ޶ȵؼõÉÙÎÞνµÄ×Ö·û´®±È½Ï£¬²éѯЧÂʱȹþÏ£±í¸ß¡£
4.1.1 Trie-treeÐÔÖÊ
ËüÓÐÈý¸ö»ù±¾µÄÐÔÖÊ£º
1£©¸ù½Úµã²»°üº¬×Ö·û£¬³ý¸ù½ÚµãÒÔÍâÿһ¸ö½Úµã¶¼Ö»°üº¬Ò»¸ö×Ö·û
2£©´Ó¸ù½Úµãµ½Ä³Ò»½Úµã£¬Â·¾¶ÉϾ¹ýµÄµÄ×Ö·ûÁ¬½ÓÆðÀ´£¬Îª¸Ä½Úµã¶ÔÓ¦µÄ×Ö·û´®¡£
3£©Ã¿¸ö½ÚµãµÄËùÓÐ×Ó½Úµã°üº¬µÄ×Ö·û¶¼²»Ïàͬ¡£
¡¡Í¼4-1 tire-tree
4.1.2 TrieÊ÷µÄ»ù±¾ÊµÏÖ
×ÖĸÊ÷µÄ²åÈ롢ɾ³ýºÍ²éÕÒ¶¼·Ç³£¼òµ¥£¬ÓÃÒ»¸öÒ»ÖØÑ»·¼´¿É£¬¼´µÚi´ÎÑ»·ÕÒµ½Ç°i¸ö×ÖĸËù¶ÔÓ¦µÄ×ÓÊ÷£¬È»ºó½øÐÐÏàÓ¦µÄ²Ù×÷¡£ÊµÏÖÕâ¿Ã×ÖĸÊ÷£¬ÎÒÃÇÓÃ×î³£¼ûµÄÊý×é±£´æ£¨¾²Ì¬¿ª±ÙÄڴ棩¼´¿É£¬µ±È»Ò²¿ÉÒÔ¿ª¶¯Ì¬µÄÖ¸ÕëÀàÐÍ£¨¶¯Ì¬¿ª±ÙÄڴ棩¡£ÖÁÓÚ½áµã¶Ô¶ù×ÓµÄÖ¸Ïò£¬Ò»°ãÓÐÈýÖÖ·½·¨£º
1£©¶Ôÿ¸ö½áµã¿ªÒ»¸ö×Öĸ¼¯´óСµÄÊý×飬¶ÔÓ¦µÄϱêÊǶù×ÓËù±íʾµÄ×Öĸ£¬ÄÚÈÝÔòÊÇÕâ¸ö¶ù×Ó¶ÔÓ¦ÔÚ´óÊý×éÉϵÄλÖ㬼´±êºÅ£»
2£©¶Ôÿ¸ö½áµã¹ÒÒ»¸öÁ´±í£¬°´Ò»¶¨Ë³Ðò¼Ç¼ÿ¸ö¶ù×ÓÊÇË£»
3£©Ê¹ÓÃ×ó¶ù×ÓÓÒÐֵܱíʾ·¨¼Ç¼Õâ¿ÃÊ÷¡£
ÈýÖÖ·½·¨£¬¸÷ÓÐÌØµã¡£µÚÒ»ÖÖÒ×ʵÏÖ£¬µ«Êµ¼ÊµÄ¿Õ¼äÒªÇó½Ï´ó£»µÚ¶þÖÖ£¬½ÏÒ×ʵÏÖ£¬¿Õ¼äÒªÇóÏà¶Ô½ÏС£¬µ«±È½Ï·Ñʱ£»µÚÈýÖÖ£¬¿Õ¼äÒªÇó×îС£¬µ«Ïà¶Ô·ÑʱÇÒ²»Ò×д¡£
4.1.2.1 ʵÏÖ·½·¨
ËÑË÷×Öµä[8]ÏîÄ¿µÄ·½·¨Îª£º
1) ´Ó¸ù½áµã¿ªÊ¼Ò»´ÎËÑË÷£»
2) È¡µÃÒª²éÕҹؼü´ÊµÄµÚÒ»¸ö×Öĸ£¬²¢¸ù¾Ý¸Ã×ÖĸѡÔñ¶ÔÓ¦µÄ×ÓÊ÷²¢×ªµ½¸Ã×ÓÊ÷¼ÌÐø½øÐмìË÷£»
3) ÔÚÏàÓ¦µÄ×ÓÊ÷ÉÏ£¬È¡µÃÒª²éÕҹؼü´ÊµÄµÚ¶þ¸ö×Öĸ,²¢½øÒ»²½Ñ¡Ôñ¶ÔÓ¦µÄ×ÓÊ÷½øÐмìË÷¡£
4) µü´ú¹ý³Ì¡¡
5) ÔÚij¸ö½áµã´¦£¬¹Ø¼ü´ÊµÄËùÓÐ×ÖĸÒѱ»È¡³ö£¬Ôò¶ÁÈ¡¸½ÔڸýáµãÉϵÄÐÅÏ¢£¬¼´Íê³É²éÕÒ¡£
ÆäËû²Ù×÷ÀàËÆ´¦Àí
4.1.2.2 TrieÔÀí
TrieµÄºËÐÄ˼ÏëÊǿռ任ʱ¼ä¡£ÀûÓÃ×Ö·û´®µÄ¹«¹²Ç°×ºÀ´½µµÍ²éѯʱ¼äµÄ¿ªÏúÒÔ´ïµ½Ìá¸ßЧÂʵÄÄ¿µÄ¡£
4.1.3 TrieÊ÷µÄ¸ß¼¶ÊµÏÖDouble-Array ʵÏÖ
¿ÉÒÔ²ÉÓÃË«Êý×飨Double-Array£©ÊµÏÖ,Èçͼ1.3¡£ÀûÓÃË«Êý×é¿ÉÒÔ´ó´ó¼õСÄÚ´æÊ¹ÓÃÁ¿£¬¾ßÌåʵÏÖ
Á½¸öÊý×飬һ¸öÊÇbase[]£¬ÁíÒ»¸öÊÇcheck[]¡£ÉèÊý×éϱêΪi£¬Èç¹ûbase[i],
check[i]¾ùΪ0£¬±íʾ¸ÃλÖÃΪ¿Õ¡£Èç¹ûbase[i]Ϊ¸ºÖµ£¬±íʾ¸Ã״̬ΪÖÕֹ̬£¨¼´´ÊÓ¡£check[i]±íʾ¸Ã״̬µÄǰһ״̬¡£
¶¨Òå 1. ¶ÔÓÚÊäÈë×Ö·û c,´Ó״̬ s ×ªÒÆµ½×´Ì¬ t,Ë«Êý×é×ÖµäÊ÷Âú×ãÈçÏÂÌõ¼þ(ͼ4-2):
check[base[s] + c] = s
base[s] + c = t

´Ó¶¨Òå1ÖУ¬ÎÒÃÇÄܵõ½²éÕÒËã·¨£¬¶ÔÓÚ¸ø¶¨µÄ״̬ s ºÍÊäÈë×Ö·û c £º
t := base[s] + c; if check[t] = s then next state := t else fail endif
ÎÒÃÇÖªµÀË«Êý×éµÄʵÏÖ·½·¨Êǵ±×´Ì¬ÓÐÐÂ×ªÒÆÊ±²Å·ÖÅä¿Õ¼ä¸øÐÂ״̬£¬»ò¿ÉÒÔ±íÊöΪֻ·ÖÅäÐèÒª×ªÒÆµÄ״̬µÄ¿Õ¼ä¡£µ±Óöµ½ÎÞ·¨Âú×ãÉÏÊöÌõ¼þʱÔÙ½øÐе÷Õû£¬Ê¹µÃÆä
base ÖµÂú×ãÉÏÊöÌõ¼þ£¬ÕâÖÖµ÷ÕûÖ»Ó°Ï쵱ǰ½ÚµãÏÂÒ»²ã½ÚµãµÄÖØ·ÖÅ䣬ÒòΪËùÓнڵãµÄµØÖ··ÖÅäÊÇ¿¿ base
Êý×éÖ¸¶¨µÄÆðʼϱêËù¾ö¶¨µÄ¡£²åÈëµÄ²Ù×÷£¬¼ÙÉèÒÔij×Ö·û¿ªÍ·µÄ base ֵΪi£¬µÚ¶þ¸ö×Ö·ûµÄ×Ö·ûÐòÁÐÂëÒÀ´ÎΪc1,
c2, c3¡cn£¬Ôò¿Ï¶¨ÒªÂú×ãbase[i+c1], check[i+c1], base[i+c2],
check[i+c2], base[i+c3], check[i+c3]¡base[i+cn],check[i+cn]¾ùΪ0¡£

ͼ4-3 Double Array ʵÏÖ
¼ÙÉ裬TireÀïÓÐn¸ö½Úµã£¬×Ö·û¼¯´óСΪm£¬ÔòDATrieµÄ¿Õ¼ä´óСÊÇn+cm£¬cÊÇÒÀÀµÓÚTrieÏ¡Êè³Ì¶ÈµÄÒ»¸öϵÊý¡£¶ø¶à·²éÕÒÊ÷µÄ¿Õ¼ä´óСÊÇnm¡£
×¢Ò⣬ÕâÀïµÄ¸´ÔӶȶ¼Êǰ´ÀëÏßËã·¨£¨offline algorithm£©¼ÆËãµÄ£¬¼´´¦ÀíʱÒѾµÃµ½Õû¸ö´Ê¿â¡£ÔÚÏßËã·¨£¨online
algorithm£©µÄ¿Õ¼ä¸´ÔÓ¶È»¹ºÍµ¥´Ê³öÏÖµÄ˳ÐòÓйأ¬Ô½ÓÐÐòµÄµ¥´Ê˳Ðò¿Õ¼äÕ¼ÓÃԽС¡£
²éÕÒËã·¨µÄ¸´ÔӶȺͱ»²éÕÒµÄ×Ö·û´®³¤¶ÈÏà¹ØµÄ£¬Õâ¸ö¸´ÔӶȺͶà·²éÕÒÊ÷ÊÇÒ»ÑùµÄ¡£
²åÈëËã·¨ÖУ¬Èç¹û³öÏÖÖØ·ÖÅäµÄÇé¿ö£¬ÎÒÃÇÒª¸½¼ÓÉÏɨÃè×Ó½ÚµãµÄʱ¼ä¸´ÔÓ¶È£¬»¹ÓÐÐÂbaseֵȷ¶¨µÄËã·¨¸´ÔÓ¶È¡£¼ÙÈçÕâ¶ùÎÒÃǶ¼ÊÇÓñ©Á¦Ëã·¨£¨forÑ»·É¨Ã裩£¬ÄDzåÈëË㷨ʱ¼ä¸´ÔÓ¶ÈÊÇO(nm
+ cm2)¡£¡£
ʵ¼Ê±àÂë¹ý³ÌÖУ¬DATrie´úÂëÄѶȴó¹ý¶à·²éÕÒÊ÷£¬Ö÷ÒªÊÇ״̬µÄ±íʾ²»ÈçÊ÷½á¹¹ÄÇÑùµÄÇåÎú£¬Ï±êºÜÈÝÒ׸ã»ìµô¡£
ÓиöµØ·½ÐèҪעÒâµÄÊÇ£¬baseÖµÕýÊý±íʾÆðÊ¼Æ«ÒÆÁ¿£¬¸ºÊý±íʾ¸Ã״̬ΪÖÕֹ̬£¬ËùÒÔÔÚ²éÕÒÐÂbaseֵʱ£¬Òª±£Ö¤²éµ½µÄÖµÊÇÕýÊý¡£
È磺¿ÕTrie״̬Ï£¬²åÈëdʱ£¬ÒòΪµÚÒ»¸ö¿ÕµØÖ·ÊÇ1£¬ËùÒԵõ½base=1-4=-3£¬ÕâÑùbaseÕý¸ºµÄº¬Òå¾Í±»ÆÆ»µÁË¡£
4.1.4 TrieÊ÷µÄÓ¦ÓÃ
TrieÊÇÒ»Öַdz£¼òµ¥¸ßЧµÄÊý¾Ý½á¹¹£¬µ«ÓдóÁ¿µÄÓ¦ÓÃʵÀý¡£
£¨1£©×Ö·û´®¼ìË÷
ÊÂÏȽ«ÒÑÖªµÄһЩ×Ö·û´®£¨×ֵ䣩µÄÓйØÐÅÏ¢±£´æµ½trieÊ÷À²éÕÒÁíÍâһЩδ֪×Ö·û´®ÊÇ·ñ³öÏÖ¹ý»òÕß³öÏÖÆµÂÊ¡£ÀýÈ磺 1£©¸ø³öN¸öµ¥´Ê×é³ÉµÄÊì´Ê±í£¬ÒÔ¼°Ò»ÆªÈ«ÓÃСдӢÎÄÊéдµÄÎÄÕ£¬ÇëÄã°´×îÔç³öÏÖµÄ˳Ðòд³öËùÓв»ÔÚÊì´Ê±íÖеÄÉú´Ê¡£ 2£©¸ø³öÒ»¸ö´Êµä£¬ÆäÖеĵ¥´ÊΪ²»Á¼µ¥´Ê¡£µ¥´Ê¾ùΪСд×Öĸ¡£ÔÙ¸ø³öÒ»¶ÎÎı¾£¬Îı¾µÄÿһÐÐÒ²ÓÉСд×Öĸ¹¹³É¡£ÅжÏÎı¾ÖÐÊÇ·ñº¬ÓÐÈκβ»Á¼µ¥´Ê¡£ÀýÈ磬ÈôrobÊDz»Á¼µ¥´Ê£¬ÄÇôÎı¾problemº¬Óв»Á¼µ¥´Ê¡£
£¨2£©×Ö·û´®×¹«¹²Ç°×º
TrieÊ÷ÀûÓöà¸ö×Ö·û´®µÄ¹«¹²Ç°×ºÀ´½ÚÊ¡´æ´¢¿Õ¼ä£¬·´Ö®£¬µ±ÎÒÃǰѴóÁ¿×Ö·û´®´æ´¢µ½Ò»¿ÃtrieÊ÷ÉÏʱ£¬ÎÒÃÇ¿ÉÒÔ¿ìËٵõ½Ä³Ð©×Ö·û´®µÄ¹«¹²Ç°×º¡£ ÀýÈ磺¸ø³öN¸öСдӢÎÄ×Öĸ´®£¬ÒÔ¼°Q¸öѯÎÊ£¬¼´Ñ¯ÎÊijÁ½¸ö´®µÄ×¹«¹²Ç°×ºµÄ³¤¶ÈÊǶàÉÙ£¿ ½â¾ö·½°¸£ºÊ×ÏȶÔËùÓеĴ®½¨Á¢Æä¶ÔÓ¦µÄ×ÖĸÊ÷¡£´Ëʱ·¢ÏÖ£¬¶ÔÓÚÁ½¸ö´®µÄ×¹«¹²Ç°×ºµÄ³¤¶È¼´ËüÃÇËùÔÚ½áµãµÄ¹«¹²×æÏȸöÊý£¬ÓÚÊÇ£¬ÎÊÌâ¾Íת»¯ÎªÁËÀëÏߣ¨Offline£©µÄ×î½ü¹«¹²×æÏÈ£¨LeastCommon
Ancestor£¬¼ò³ÆLCA£©ÎÊÌâ¡£ ¶ø×î½ü¹«¹²×æÏÈÎÊÌâͬÑùÊÇÒ»¸ö¾µäÎÊÌ⣬¿ÉÒÔÓÃÏÂÃæ¼¸ÖÖ·½·¨£º 1£©ÀûÓò¢²é¼¯£¨Disjoint Set£©£¬¿ÉÒÔ²ÉÓòÉÓþµäµÄTarjanËã·¨£» 2£©Çó³ö×ÖĸÊ÷µÄÅ·ÀÐòÁУ¨Euler Sequence£©ºó£¬¾Í¿ÉÒÔתΪ¾µäµÄ×îСֵ²éѯ£¨Range
Minimum Query£¬¼ò³ÆRMQ£©ÎÊÌâ
£¨3£©ÅÅÐò
TrieÊ÷ÊÇÒ»¿Ã¶à²æÊ÷£¬Ö»ÒªÏÈÐò±éÀúÕû¿ÃÊ÷£¬Êä³öÏàÓ¦µÄ×Ö·û´®±ãÊǰ´×ÖµäÐòÅÅÐòµÄ½á¹û¡£ÀýÈ磺¸øÄãN¸ö»¥²»ÏàͬµÄ½öÓÉÒ»¸öµ¥´Ê¹¹³ÉµÄÓ¢ÎÄÃû£¬ÈÃÄ㽫ËüÃǰ´×ÖµäÐò´ÓСµ½´óÅÅÐòÊä³ö¡£
£¨4£©×÷ΪÆäËûÊý¾Ý½á¹¹ºÍËã·¨µÄ¸¨Öú½á¹¹£¬Èçºó׺Ê÷£¬AC×Ô¶¯»úµÈ
4.1.5 TrieÊ÷¸´ÔÓ¶È·ÖÎö
£¨1£©²åÈë¡¢²éÕÒµÄʱ¼ä¸´ÔӶȾùΪO(N)£¬ÆäÖÐNΪ×Ö·û´®³¤¶È¡£ £¨2£©¿Õ¼ä¸´ÔÓ¶ÈÊÇ26^n¼¶±ðµÄ£¬·Ç³£ÅӴ󣨿ɲÉÓÃË«Êý×éʵÏÖ¸ÄÉÆ£©¡£
4.1.6 ×ܽá
TrieÊ÷ÊÇÒ»Öַdz£ÖØÒªµÄÊý¾Ý½á¹¹£¬ËüÔÚÐÅÏ¢¼ìË÷£¬×Ö·û´®Æ¥ÅäµÈÁìÓòÓй㷺µÄÓ¦Óã¬Í¬Ê±£¬ËüÒ²ÊǺܶàËã·¨ºÍ¸´ÔÓÊý¾Ý½á¹¹µÄ»ù´¡£¬Èçºó׺Ê÷£¬AC×Ô¶¯»úµÈ¡£
4.2 TrieMemory
Trie Memory[9]ÊÇÒ»ÖÖÔÚÄÚ´æÖд洢ºÍ¼ìË÷ÐÅÏ¢µÄ·½Ê½£¬ÕâÖÖ·½Ê½µÄÓŵãÊÇ·ÃÎÊËٶȿ죬¾ßÓÐÈßÓà´æ´¢ÐÅÏ¢µÄÓŵ㣬Ö÷ÒªµÄȱµãÊÇ´æ´¢¿Õ¼äÀûÓÃÂʺܵ͡£
4.2.1 »ù±¾µÄTrie MemoryÄ£ÐÍ
¼ÙÉèÎÒÃÇÐèÒª¸ú×ÙһϵÁеĵ¥´Ê¼¯ºÏ£¬ÕâЩ¼¯ºÏÊÇ×Öĸ×é³ÉµÄÐòÁС£ÕâЩµ¥´ÊÐòÁÐÓи÷ÖÖ¸÷ÑùµÄ³¤¶È£¬ÎÒÃDZØÐë¼ÇסµÄÊÇÕâЩ×Öĸ×é³ÉµÄÓÐÏÞÐòÁÐÔÚÕâ¸ö¼¯ºÏÖС£×ܵÃÀ´Ëµ£¬ÎÒÃÇÐèÒªÅжÏÒ»¸öÐòÁÐÊDz»ÊÇÕâ¸ö¼¯ºÏµÄ³ÉÔ±¡£ ¸Õ¿ªÊ¼trie½ö½öÊÇregister×é³ÉµÄÒ»¸ö¼¯ºÏ£¬³ý´ËÖ®Í⻹ÓÐÁ½¸öregister£¬Ò»¸öÊǦÁÁíÒ»¸öÊǦģ¬Ã¿Ò»¸öregister¶¼ÓÐcellÀ´´æ´¢Õû¸ö×Öĸ±í£¬Èç¹ûÎÒÃÇÒª´æ´¢¡°space¡±µÄ»°£¬Ã¿¸öregister±ØÐëÓµÓÐ27¸öcell¡£ ÿһ¸öcell¶¼ÓпռäÀ´´æ´¢ÆäËüregisterÔÚÄÚ´æÖеĵØÖ·£¬trieÖеÄcell»¹Ã»ÓÐÓÃÀ´´æ´¢ÐÅÏ¢£¬Í¨³£°üº¬µÄÊÇregister
¦ÁµÄµØÖ·ÐÅÏ¢¡£Ò»¸öcellÈç¹û°üº¬ÁË·Çregister ¦ÁµÄregisterµØÖ·£¬ÔòËü±íʾ´æ´¢ÁËÐÅÏ¢£¬ÕâЩÐÅÏ¢´ú±íÁËÕâ¸öcellµÄÃû³Æ£¬¡°A¡±±íʾA
cell,¡°B¡±±íʾB cell¡£ÏÂÒ»¸öregisterµÄµØÖ·ÔÚÐòÁÐÖС£ ÏÂÃæÓÃÒ»¸öÀý×Ó(ͼ2.1)À´ËµÃ÷£¬ÎªÁËÈÃÀý×Ó¼òµ¥Ð©£¬ÎÒÃÇʹÓÃ×Öĸ±íµÄǰ5¸ö×Ö·ûÀ´±íʾÕûÌ塣ȻºóÓ茱íʾ¡°space¡±£¬¼ÙÉèÎÒÃÇÏë´æ´¢DAB,BAD,BADE,BE,BED,BEAD,CAB,CADºÍA£¬½ÓÏÂÀ´ÓÃͼÀ´ËµÃ÷Õû¸öÁ÷³Ì¡£ÔÚͼÖÐÿһÐдú±íÒ»¸öregister£¬Ã¿¸öregisterÓÐ6¸öcell,×îºóÒ»Ðдú±íµÚÈý¸öÌØÊâµÄregister½Ð×öportal
register,ÊÇÎÒÃǽøÈëϵͳÄÚ´æµÄͨµÀËü³ýÁËÊÇÈë¿ÚÍ⣬ҲºÍÆäËüregisterÊÇÒ»ÑùµÄ¡£ÆäËüregisterÊDZàºÅµÄ¡£register
¦Á½«»áÑ¡ÔñËüÃÇ¡£¸Õ¿ªÊ¼µÄʱºò register ¦ÁÊÇregister 2¡£

ͼ4-4 »ù±¾Tire MemoryÄ£ÐÍ
ΪÁË´æ´¢DAB£¬ÎÒÃÇÒýÈëµØÖ·¡°2¡±½øÈëportal registerµÄD µ¥Ôª¸ñ£¬È»ºóÎÒÃÇÒÆ¶¯µ½register
2È»ºóÒýÈëµØÖ·¡°3¡±µ½Aµ¥Ôª¸ñ£¬È»ºóÎÒÃǽøÈëµ½register 3ºó°ÑµØÖ·¡°4¡±·ÅÈëµ¥Ôª¸ñB£¬×îºóÎÒÃÇÒÆ¶¯µ½register
4 ²¢ÇҰѵØÖ·¡°1¡±·ÅÈ먌µ¥Ôª£¬ËüÊÇÖÕÖ¹²ÎÊý£¬ÖÁ´ËDAB´æ´¢½áÊø¡£È»ºóÎÒÃÇתµ½µÚ¶þ¸öµ¥´ÊBAD£¬ÒýÈëµØÖ·¡°5¡±½øÈëportal
registerµÄBµ¥Ôª¸ñÀ´±íʾ×ÖĸB£¬È»ºóµ½register 5µÄAµ¥Ôª¸ñдÈëµØÖ·¡°6¡±£¬ÔÙµ½register
6µÄDµ¥Ôª¸ñдÈëµØÖ·¡°7¡±£¬×îºóµ½register 7µÄ¨Œµ¥Ôª¸ñдÈëµØÖ·¡°1¡±¡£µ±ÎÒÃÇ¿ªÊ¼´æ´¢BADEʱ£¬ÎÒÃÇ·¢ÏÖB,A,DÒѾÔÚtrieÖÐÁË£¬Òò´ËÎÒÃÇÑØ×ÅÒѾ´æÔÚµÄBADµÄ·¾¶µ½register
7È»ºóÒýÈëµØÖ·¡°8¡±µ½µ¥Ôª¸ñEÖÐÈ¥£¬È»ºó°ÑµØÖ·¡°1¡±·ÅÈëregister 8µÄ¨Œµ¥Ôª¡£
4.2.2 RegisterµÄÀàÐÍ
ÔÚ¸Õ²ÅÌáµ½µÄ½á¹¹ÖÐÎÒÃÇ¿ÉÒÔ°Ñregister·ÖΪ4ÖÖÀàÐÍ£º 1£©¦Á(address) registerÀ´Ö¸ÏòÏÂÒ»¸ö´æ´¢ÐÅÏ¢µÄµØÖ· 2£©¦Ä(deletion) register 3£©¦Í(next) register£¬ÏÂÒ»²½½«Òª´æ´¢µÄÐÅÏ¢(ÔÚ¿ÕÄÚ´æÖУ¬ËüÊÇportal register) 4£©¦Ö(exterior)ÀàÐͦÖÊÇËùÓÐregisterÖл¹Ã»ÓнÓÊÜ´æ´¢ÐÅÏ¢²¢ÇÒûÓб»Ö¸ÏòΪÏÂÒ»¸ö´æ´¢Î»ÖõÄregister¡£ 5£©¦Ï(occupied)ÀàÐͦÏÊÇ´æÓÐÐÅÏ¢µÄregister
4.2.3 TrieµÄ¶ÁºÍд
ÔÚÉÏÊöµÄËùÓеÄregisterÖгýÁ˦ֶ¼ÔÚtrieÖУ¬´æ´¢ºÍ¶ÁÈ¡²Ù×÷ÏÖÔÚÄܹ»±»¼òµ¥µÄ¹«Æ½µÄ¶¨ÒåÈçÏ¡£
4.2.3.1 д²Ù×÷
1£©°ÑµÚi¸ö²ÎÊý×Ö·û´«ÈëÏÂÒ»¸öregister£¬Èç¹ûÊǵÚÒ»¸ö×Ö·û£¬ÔòÊÇportal register 2£©Ñ¡Ôñ¶ÔÓ¦×Ö·û´®µÄµÄcell,Èç¹ûµÚi¸ö²ÎÊý×Ö·ûÊÇ×Öĸ±íµÄµÚj¸ö×Ö·û£¬Ñ¡ÔñµÚj¸öcell¡£ 3£©¼ì²âÀ´×ÔµÚi¸öµ¥ÔªµÄÁª½á 4£©Èç¹ûÕâÖÖÁª½áʹµÃregister ¦Á£º a£© ͨ¹ý¦Áregister°ÑÁª½áͶÉäµ½Á´½ÓµÄÍ·²¿£¬ÕâÑù¾Í¿ÉÒÔ´æ´¢ÐÅÏ¢¡£ b)ͶÉä´Ó¦Áregisterµ½Á´½ÓÍ·²¿µÄÁª½áÀ´´´½¨Ò»¸ö¡°next¡±register(¦Í) c)×îºó£¬°ÑËùÓеĴӦͷ¢³öÀ´µÄÁª½áÖ¸Ïò¦Áregister¡£ 5£©Èç¹ûÔ´ÓÚµÚj¸öcellµÄÁª½áÖ¸Ïò·Ç ¦ÁregisterµÄ»°£¬Òƶ¯µ½ÄǸöregisterÈ¥£º a£© Èç¹ûÊǵÚÒ»¸öregister£¬Õâ²ÎÊýÊÇÒ»¸ö´æ´¢¼¯ºÏµÄ³ÉÔ±(½áÊøÁ÷³Ì)¡£ b£©Èç¹û²»ÊÇregister 1µÄ»°£¬i¼Ó1²¢ÇÒתµ½µÚ¶þ²½È¥¡£
4.2.3.2 ¶Á²Ù×÷
ʹÓÃÏàͬµÄÁ÷³Ì£¬µ«ÊDz»ÒªÊ¹ÓÃͶÉ䣬²»ÒªÍ¶ÉäÈκιØÏµ£¬Èç¹ûÁª½áÖ¸Ïòregister 1£¬ÔòÕâ¸ö²ÎÊýÊÇ´æ´¢¼¯ºÏµÄÒ»¸ö³ÉÔ±£¬Èç¹ûÈκεãµÄÁª½áÖ¸Ïò¦Áregister,»»¾ä»°ËµÕâ¸ö²ÎÊý²»ÊÇ´æ´¢¼¯ºÏµÄ³ÉÔ±¡£
5 HASHË÷Òý
HASH¾ÍÊǰѹؼü´ÊÖ±½ÓÓ³ÉäΪ´æ´¢µØÖ·£¬´ïµ½¿ìËÙѰַµÄÄ¿µÄ£¬¼´Addr=H(key)£¬ÆäÖÐkeyΪ¹Ø¼ü´Ê£»HΪ¹þÏ£º¯Êý¡£Ö÷ÒªÓÐÒÔϼ¸ÖÖ³£ÓõĹþÏ£º¯Êý£º 1)³ýÁôÓàÊý·¨(DivisionMethod)£¬H(key)=keyMOD p£¬pÒ»°ãΪÖÊÊý£» 2)Ëæ»úÊý·¨(RandomMethod)£¬H(key)=random(key)£¬randomÎªËæ»úº¯Êý£» 3)ƽ·½È¡Öз¨(MidsquareMethod)¡£ HASHË÷Òý½á¹¹²»ÐèÒª¶îÍâµÄ´æ´¢¿Õ¼ä£¬²¢ÇÒÄܹ»ÔÚO(1)µÄʱ¼ä¸´ÔÓ¶ÈÏÂ׼ȷ¶¨Î»µ½Ëù²éÕÒµÄÊý¾Ý£¬½«´ÅÅÌÊý¾Ý¿âÖеÄÊý¾Ý²éÕÒʱ¼ä´ú¼ÛÓÅ»¯ÖÁ×îС¡£HashË÷Òý½á¹¹ÓÉÓÚÒÔÉÏÓŵãÔÚ´ÅÅÌÊý¾Ý¿âÖй㷺µÄÔËÓ᣾Àú³¤¾ÃµÄÑо¿£¬ÏȺó·¢Õ¹³öÁËÁ´½ÓͰ¹þÏ£(chainedbucket
hash)[10]£¬¿ÉÀ©Õ¹¹þÏ£(extendible hash)[11]¡¢ÏßÐÔ¹þÏ£(linearhash)[12]ºÍÐÞÕýµÄÏßÐÔ¹þÏ£(modified
linear hash)[13]¡£µ«ÊÇÕâЩ¹þÏ£Ëã·¨ËäÈ»Õë¶ÔÄÚ´æÊý¾Ý¿â½øÐÐÁËÉÙÐíÓÅ»¯£¬µ«ÊÇÓ봫ͳÊý¾Ý¿âÖÐËùÓõĹþÏ£Ë㷨ûÓÐÃ÷ÏÔ²»Í¬¡£µ½ÁË2007Ä꣬KennethA.
RossÌá³öÁË»ùÓÚÏÖ´ú´¦ÀíÆ÷µÄHashԤȡËã·¨[14]½«SIMDÖ¸ÁÈÚÈëµ½HashËã·¨ÖУ¬²ÅÕæÕý´ÓÄÚ´æË÷ÒýµÄ½Ç¶È¸Ä½øÁ˹þÏ£Ëã·¨£¬ÌáÉýÊý¾Ý×éÖ¯µÄЧÂÊ¡£
5.1 Á´½ÓͰ¹þÏ£
Á´½ÓͰ¹þÏ££¨Í¼5-1£©ÊÇÒ»¸ö¾²Ì¬µÄ½á¹¹£¬¿ÉÓÃÓÚÄÚ´æÖÐÓë´ÅÅÌÖС£ÒòΪËüÊǾ²Ì¬½á¹¹£¬²»ÓöÔÊý¾Ý½øÐÐÖØ×éÖ¯£¬ËùÒÔËüËٶȺܿ졣µ«ÕâÒ²ÊÇËüµÄȱÏÝ£¬Ãæ¶Ô¶¯Ì¬Êý¾Ý£¬¾ÍÏԵò»ºÏÊÊÁË£¬ÒòΪÁ´½ÓͰ¹þÏ£±ØÐëÔÚʹÓÃ֮ǰ֪µÀ¹þÏ£±íµÄ´óС£¬¶øÕâǡǡºÜÄÑÔ¤²â¡£Èç¹ûÔ¤²âµÄ±í´óС¹ýС£¬ÆäÐÔÄÜ»á´óÊÜÓ°Ï죻Èç¹û¹ý´ó£¬¿Õ¼äÀ˷ѽÏΪÑÏÖØ¡£×îºÃÇé¿öÏ£¬ËüÖ»ÓÐһЩ¿Õ¼äµÄÀË·Ñ£¬ÓÃÀ´´æ·ÅÖ¸ÏòÏÂÒ»¸öͰµÄÖ¸Õë¡£

5.2 ¿ÉÀ©Õ¹¹þÏ£
¿ÉÀ©Õ¹¹þÏ££¨Í¼5-2£©ÒýÈëÁËĿ¼ÎļþµÄ¸ÅÄ²ÉÓÿÉËæÊý¾ÝÔö³¤µÄ¶¯Ì¬¹þÏ£±í£¬Òò´Ë¿Ë·þÁËÁ´½ÓͰ¹þÏ£µÄȱÏÝ£¬Æä¹þÏ£±í´óС²»ÐèÒªÔ¤ÏÈÖªµÀ£¬Ò»¸ö¹þÏ£½Úµã°üº¬¶à¸öÏµ±½ÚµãÊýÁ¿Òç³öʱ½«Æä·ÖÁÑΪÁ½¸ö½Úµã¡£Ä¿Â¼°´2µÄÖ¸Êý±¶Ôö³¤£¬µ±Ò»¸ö½Úµã×°Âú¶øÇÒµ½´ïÁËÒ»¸öÌØ¶¨µÄĿ¼´óСĿ¼¾Í»á±¶Ôö¡£¹þÏ£º¯ÊýΪÿ¸ö¼ü¼ÆËãÒ»¸öKλµÄ¶þ½øÖÆÐòÁУ¬Í°µÄÊýÁ¿×ÜÊÇʹÓôÓÐòÁеÚһλ»òÕß×îºóһλËãÆðµÄÈô¸Éλ[]¡£µ«ÊÇ¿ÉÀ©Õ¹¹þÏ£µÄÒ»¸öÎÊÌâÊÇÈÎÒâÒ»¸ö½Úµã¶¼»áÒýÆðĿ¼µÄ·ÖÁÑ£¬µ±¹þÏ£º¯Êý²»¹»Ëæ»úʱ£¬Ä¿Â¼ºÜ¿ÉÄÜÔö³¤µÄºÜ¾Þ´ó¡£

5.3 ÏßÐÔ¹þÏ£
ÏßÐÔ¹þÏ££¨Í¼5-3£©Ò²Ê¹Óö¯Ì¬µÄ¹þÏ£±í£¬µ«ÊÇͬ¿ÉÀ©Õ¹¹þÏ£Óнϴó²î±ð¡£ÏßÐÔ¹þϣѡÔñͰÊý×ÜÊÇʹ´æ´¢¿éµÄƽ¾ù¼Ç¼±£³ÖÓëÈÝÁ¿³ÉÒ»¸ö¹Ì¶¨µÄ±ÈÀý¡£¶øÇÒ¹þϣͰ²»×ÜÊÇ¿ÉÒÔ·ÖÁÑ£¬ÔÊÐíÓÐÒç³ö¿é¡£µ±²åÈëµÄ¼Ç¼ûÓжÔÓ¦µÄͰ£¬½«Æä¹þÏ£ÖµÊ×λ¸ÄΪ0£¬ÔٴβåÈ룬·ñÔòÖ±½Ó²åÈë¶ÔӦͰ»òÆäÒç³ö¿éÖС£µ±¼Ç¼ÊýÁ¿±ÈÈÝÁ¿´ïµ½Ò»¸öãÐÖµ£¬Ôö¼ÓÒ»¸öͰ£¬ÔÙ·ÖÅä¡£Ïà¶ÔÓÚ¿ÉÀ©Õ¹¹þÏ££¬ÏßÐÔ¹þÏ£µÄÔö³¤½ÏΪ»ºÂý£¬ÖØ×éÖ¯µÄ´ÎÊýºÍ´ú¼Û¶¼½ÏС¡£Í¬Ê±£¬ÏßÐÔÉ¢Áв»ÐèÒª´æ·ÅÊý¾ÝͰָÕëµÄרÃÅĿ¼ÏÇÒÄܸü×ÔÈ»µÄ´¦ÀíÊý¾ÝͰÒÑÂúµÄÇé¿ö£¬ÔÊÐí¸üÁé»îµÄÑ¡ÔñͰ·ÖÁѵÄʱ»ú¡£

5.4 ÐÞÕýµÄÏßÐÔ¹þÏ£
ÐÞÕýµÄÏßÐÔ¹þÏ£Ïà¶ÔÓÚÏßÐÔ¹þÏ£Ö÷ÒªÃæÏòÄÚ´æ»·¾³¡£Í¨¹ýʹÓøü´óµÄÁ¬Ðø½ÚµãÌæ´úĿ¼£¬ÆÕͨµÄÏßÐÔ¹þÏ£ÓÉÓÚÓÐ¿Õ½Úµã¶øÀ˷ѿռ䡣¶øÇÒ£¬³ý·ÇÓÐÒ»¸öÇÉÃîµÄ·½°¸½â¾öDZÔÚµÄÐéÄâÄÚ´æÓ³Éä»úÖÆÎÊÌ⣬²»È»Ã¿´ÎĿ¼Ôö³¤Ê±ÄǸöÁ¬ÐøµÄ½Úµã¶¼Òª±»¿½±´µ½Ò»¸ö¸ü´óµÄÄÚ´æ¿é¡£ÐÞÕýµÄÏßÐÔ¹þÏ£²ÉÓøú¿ÉÀ©Õ¹¹þÏ£Ò»ÑùµÄĿ¼£¬³ýÁËĿ¼ΪÏßÐÔÔö³¤µÄ£¬Á´½ÓµÄÊǵ¥¸öÏîÄ¿µÄ½ÚµãºÍ·ÖÅäÄÚ´æÊÇ´ÓÒ»¸ö³£¹æµÄÄÚ´æ³Ø¡£Õâ¸öËã·¨½Úµã·ÖÁѵÄ×¼ÔòÊÇ»ùÓÚÐÔÄÜ£¬¾ÙÀýÀ´Ëµ£¬¼à¿Ø¹þÏ£Á´µÄƽ¾ù³¤¶È±È¼à¿Ø´æ´¢ÀûÓÃÂÊÄܹ»¸üÖ±½ÓµÄ¿ØÖÆÆ½¾ùËÑË÷ºÍ¸üÐÂʱ¼ä[13]¡£
5.5 HashԤȡËã·¨
HashԤȡËã·¨ÃæÏòµÄÊǼüºÍ¹þÏ£Öµ¶¼ÊÇ32λµÄ³¡¾°£¬ÌصضÔÄÚ´æ»·¾³½øÐÐÁËÓÅ»¯¡£´ËË㷨ʹÓó˷¨É¢ÁУ¬ÕâÖÖ·½·¨Ê®·ÖÆÕ±é¡¢¼ÆËã¸ßЧ£¬¸üÖØÒªµÄÊÇÊÊÓÃÓÚʸÁ¿£¬´ïµ½ÁËÒ»´Î¼ÆËã¶à¸ö¹þÏ£º¯ÊýµÄÄ¿µÄ[14]¡£Õë¶ÔÏÖ´ú´¦ÀíÆ÷µÄSIMD¼Ü¹¹£¬½«¼üÖµÓë¹þÏ£Öµ¹²Í¬·ÅÔÚÒ»¸öÖ¸Áîµ±ÖУ¬´ïµ½´ó´ó¼õÉÙÖ¸ÁîÊýµÄÄ¿µÄ£¬Áîÿ´ÎËùÐèµÄÊý¾Ý³¤¶ÈÇ¡ºÃµÈÓÚL2µÄcacheline£¬´ó´ó½µµÍÁËÐÔÄÜ´ú¼Û£¬ÔÚÄÚ´æ»·¾³ÖУ¬´ó´óÌá¸ßÁËcacheµÄÐÔÄÜ¡£ |