A CSB + -Tree is a balanced multi-way search tree.

!#"$ &%('$)*,+-/. 0)*/

213 4)5 6 78:9;)7<

=>@?BACEDGFIHJ>LK0F@F*>*KNMPOJQ@RTSJUTO4V7W@X

Y[Z@?\CEDGFI][C;D^F@?_@`aFbMOJQ@RJSTUTO4V7S@X

m n

epo5qsr/ZLtuZLC;CEKgvwo@exC^ydfLrzCaZ5{|fE>*f*FLC}?\Ca?\oe~_5{€rkArz‚;>5{€rzo4ZrkZ

c3oƒK@C*ePZ]„>5{…>†*>LD‡Cˆƒ~LD…{‰C*?ŠD

m

]‹rŒ C*eC*ZL{Ž‹@*eo@>LfaFLC;D

 ‘a’…“‡”…•–“P—;˜‰™,“š—;›‰™šœ˜…ž• Ÿ¡™p¢P£-›…“¤¢¤›ž£•P™

 ¥@• ¦b§’¤¨—;›¢ª©/—ž£Tž’¢,’[£•“P—ž£€™

m ¹º

Y»DGJCEC;K@D¼F*>5½LCd†JC;CaZgr/ZLf*eCE>*Džr/ZLtg>L{Ž>g?_LfaFBv >*D‰{‰Cae„e,>5{‰C

{žF*>@Zg?ŠC*?Šo@ep~¾DGTC;CEK@D

m ¹

o4ZLfaA_LDGro4Zƒ¿‹r/?aeoa½Tr/ZLt}f7>LfaFLCd†TC*F*>L½TroerzDŽtToªr/ZLt3{…oI†TC>@Z

m

ˆ?Š>@AkA/h4v >LD…{Žˆ–Á|cÂ?ŠC*?Šo@e¤rCED|{žF*>5{\rk?B*eoJ½LC3TC*epvwo@eP?Š>ZLf;C}†;~

FLo4AK4r/ZLtIeC;fEC*Z5{žA~eC^vwCaeC*ZLfEC;KIK>5{…>

m

c3C*?Šo@ep~eC;vwC*eC*ZLfECT¿

¹

>LfaFLC}ÃÄr{Gh

¹

>*f*FLCgcgrD‡D

m º

>ae,>@?ŠC^{‰CaepDE¿

 ‘a’ž¬…’…“‰š¢-¨

 Å §—G“‡Æ–™ šÇ•Èɓ’…“‡”…•:§šœ˜…•Ê

m ¹

>*f*FLCBˆªCaZLDžr{€r½LCBˆªC7>aef*FbM

¹

ˆ0ˆX‹{žeC;CED

 «^’…“‡”„˜‰—Gž•–“P—;˜¢’€šz˜‰™0—;˜ž§¨[Ƥ•¤¨‰™’ž˜…‹˜‰—‹¬‡—Gšœ˜¢•‡£°™

 ¥T—Gž•P™’£•–™p¢—ž£•Ž§•¤Ì…•…§7­P¨[§•¤Ì…•‡§€©£°—;Ï<§•¤©¢4¢—Уlš¯;”¢

 Ë£/š¢P”žÏ•¤¢wš“—;¬•‡£’¢ š—^˜‰™—;˜¡—‡®L™,•¤¢p™¢p—±L˜…[“‡”šœ§Ð˜‰—Gž•P™

 Å •¤¢¢,•‡£JÑE•’‡£k“…”ÄÒ;•‡£œ©/—ž£-ϒG˜‰“•¡’G˜…Ä‘*’‡“‡”‰•§šœ˜…•¡›¢ šœ§šÇP’¢ š—;˜ ¢P”…’ž˜„ÓªÔ7ÕÖT£••P™

m ¹

>*f*FLC}A°r/ZLC¼Džrz‚^C5á3V5SI†;~5{‰CED^h=:C^~¾DGr‚;C7á

º

oªrkZ5{‰Cae:Džrz‚^C5áWN†;~5{‰C;D

ˆ4CE>aef*F`GC^~aáÀR

Ü

m n o@>@A

 äL•¤¢’€šz˜¯—ž—GÄ“’…“‡”…•­•‡”…’Ìš—;›ž£*—‡©ª‘aÑ;Ñ^ÕÖT£••P™0¦”šœ§• ’¢4¢P”…• ™’Gϕ ¢ šœÏ•

­•‰šœ˜‰¯’G­ž§•¢—™P›ž¬ž¬‡—ž£°¢šœ˜…“…£k•…Ï•‡˜¢,’ž§E›ž¬ž’‰¢•P™

 ֔š™0¦’P¨[š¢ª¦šœ§§E­•:›‰™,•¤©p›ž§G• Ì‡•…˜¡©/—ž£ª˜‰—;˜Õ ÙƒÑEÑ[¦—ž£-Ƨ—’‡€™

m å K@C7>

 æJ™•ÒE’‡£°¢wš’ž§7Ò^—Gšœ˜¢•‡£ª«5§šzϚz˜…’¢ š—^˜¡ÖL•P“‡”ž˜šçE›…•

 è@’Ì…•–©/•¤¦ƒ•‡£ª¬—žšœ˜¢,•…£™ ¬•‡£ƒ˜‰—Gž• ¢¤”…’G˜¡’ÄÓ4ÔEÕpÖJ£k•P•–™—ŽÏ—ž£•–™P¬…’‡“P• ©/—ž£ªÆ¤•¤¨‰™

 æJ™•§šœÏ–š¢•’žÏ—^›ž˜¢0—…©ƒ’£/š¢¤”žÏ•¤¢ š“—;˜¡—‡®L™,•¤¢p™¢p—[“P—^Ï¡¬€•‡˜‰™’‰¢• ©/—ž£ª§•P™™

˜ž›žÏ¡­€•…£a—…©¬‡—Gšœ˜¢,•‡£°™

m

ˆª{že¤_Lf;{ž_@epC

 ÒJ›¢0’G§§ž“…”šœ§Ä˜‰—^ž•¤™—‡©’x¯GšÌ…•…˜„˜‰—Gž•¡šœ˜x’Äéƒê^ëžìíaî/êGï‰ð

 Ñ^¢p—ž£•˜‰—Gž•P™0¦š¢P”šz˜¡’„˜‰—Gž•–¯^£°—;›ž¬:“P—;˜¢wš¯;›—;›‰™P§¨x’ž˜…‹›‰™,•–—…®L™,•¤¢

m ¹

>*f*FLC}A°r/ZLC¼Džrz‚^C5á3óoƒK@CDžrz‚^C5áÀiJWu†;~5{‰CED

m

=xC;~3>@ZLKgfaFTrkAKNToƒr/Z5{‰CaexCE>*f*F3oƒfEf*_@;~¾Wu†;~5{‰C;D

m

=xC;~LDJCae„ZLoƒK@CÀvwo@eÐô–õö÷epCEC7áÀø

m

=xC;~LDJCae„ZLoƒK@CÀvwo@e

¹

ˆ–ô

õ

ö÷:eC;C5á3V7W

m åZ ¹

ˆ–ôõö÷:eC;CED^h–Z@_@?B†JCaexoJv:f7>LfaFLC}A°r/ZLCEDŽ{‰ou†JC¼D…C7>aef*FLCEKb>JepC

ù Î ¡ +»"$sÛ\Ü[Ý;ÞÀƒ

incremental updates of B ⁺ -Trees. We achieve this goal by balancing the best features of the two index structures. Our tree structure, which we call a CSB ⁺ -Tree, is similar to a B ⁺ -Tree in the way it handles updates. However, a CSB ⁺ -Tree has fewer pointers per node than a B ⁺ -Tree. By having fewer pointers per node, we have more room for keys and hence better cache performance.

We get away with fewer pointers by using a limited amount of arithmetic on array offsets, together with the pointers, to identify child nodes.

For simplicity of presentation, we initially present a version of CSB ⁺ -Trees in which a node contains exactly one pointer. Sometimes we simply use the term CSB ⁺ -Tree to refer to this version when the context is clear. In Section 3.2 we will describe variants with more pointers per node. The number of pointers per node is a parameter that can be tuned to obtain good performance under particular workloads. We describe another variant of CSB ⁺ - Trees that further reduces split cost in Section 3.3.

3.1 Cache Sensitive B ⁺ -Trees with One Child Pointer

A CSB ⁺ -Tree is a balanced multi-way search tree.

Every node in a CSB ⁺ -Tree of order d contains m keys, where d <= m <= 2d. A CSB ⁺ -Tree puts all the child nodes of any given node into a node group. Nodes within a node group are stored contiguously and can be accessed using an offset to the first node in the group. ¹ Each internal node in a CSB ⁺ -Tree has the following structure:

nKeys :number of keys in the node firstChild :pointer to the first child node keyList[2d] :a list of keys.

Each leaf node stores a list of <key, tuple ID> pairs, the number of these pairs, and two sibling pointers. ² Since a CSB ⁺ -Tree node needs to store just one child pointer explicitly, it can store more keys per node than a B ⁺ -Tree. For example, if the node size (and cache line size) is 64 bytes and a key and a child pointer each occupies 4 bytes, then a B ⁺ -Tree can only hold 7 keys per node whereas a CSB ⁺ -Tree can have 14 keys per node. This gives CSB ⁺ -Tree two kinds of benefit: (a) a cache line can satisfy (almost) one more level of comparisons and thus the number of cache lines needed for a search is fewer;

(b) the fan out of each node is larger, which means

1 [O’N92] also considers grouping nodes together in a disk- based B ⁺ -Tree to improve I/O performance.

2 see Section 5 for further discussion of how leaf nodes can be implemented.

it uses less space. Figure 2 shows a CSB ⁺ -Tree of order 1. Each dashed box represents a node group.

The arrows from the internal nodes represent the first child pointers. All the nodes within a node group are physically adjacent to each other. In this example, a node group can have no more than three nodes within it. Note that grouping is just a physical ordering property, and does not have any associated space overhead.

2 3

25 30

5 7 12 13 16 19 20 22 24 25 27 30 31 33 36 39

3 13 19

22

33 7

Figure 2: A CSB ⁺ -Tree of Order 1 3.1.1 Operations on a CSB ⁺ -Tree

In this section, we consider bulkload, search, insert and delete operations on CSB ⁺ -Trees.

Bulkload. A typical bulkloading algorithm for B ⁺ -Trees is to keep inserting sorted leaf entries into the rightmost path from the root. However, this method can be expensive if used for CSB ⁺ -Trees since nodes in the same node group are not created sequentially. A more efficient bulkloading method for CSB ⁺ -Trees is to build the index structure level by level. We allocate space for all the leaf entries.

We then calculate how many nodes are needed in the higher level and then allocate a continuous chunk of space for all the nodes in this level. We then fill in the entries of nodes in the higher level by copying the largest value in each node in the lower level. We also set the first child pointer in each higher level node. We repeat the process until the higher level has only one node and this node is designated as the root. Since all the nodes in the same level are contiguous when they are created, we don’t have to do any additional copying to form a node group.

Search. Searching a CSB ⁺ -Tree is similar to searching a B ⁺ -Tree. Once we have determined the rightmost key K in the node that is smaller than the search key, we simply add the offset of K to the first-child pointer to get the address of the child node. (For values less than or equal to the leftmost key, the offset is 0.) So, for example, if

478

m

ô_@A`aAoT>*K

 ˧§—G“’¢,•™P¬…’‡“P• ©/—ž£ª§•’©@•‡˜¢¤£lš•P™

 ‘a’ž§“‡›ž§’‰¢•x”‰—¦Ï’ž˜¨„˜‰—Gž•P™’£•˜…•P•ž•[’¢ ”š¯;”…•…£ƒ§• Ì…•‡§G’ž˜…[’ž§§—G“’¢,•

¢P”‰•‡Ï“P—^˜¢ š¯;›‰—;›‰™¤§¨

 ü^šœ§§^šz˜¢¤”…•–•‡˜¢P£/š•¤™’¢ ”š¯^”…•‡£§•¤Ì…•‡§ž’G¬ž¬‡£—^¬£/š’¢,•…§¨¡’G˜…™,•¤¢0±L£°™p¢“‡”šz§

¬‡—Gšœ˜¢•‡£°™

 ‘*—^˜¢ šœ˜ž›…•¦š¢¤”¢P”…• ™,’žÏ•¬£°—G“•P™p™¡›ž˜¢wšœ§—;˜ž§¨x—^˜…•˜‰—Gž•£•‡Ï’šœ˜‰™š°ý•þL£°—ž—‡¢

m

ˆ4CE>aef*F

 Ñ5šzϖšœ§’‡£5¢—

Å Ô ÕÖT£••–™,•’£“‡”:’ž§¯—ž£/š¢P”žÏ

 ÿ…—G“’‰¢•£/š¯;”¢¤Ï—™p¢ Ƥ•¤¨šz˜¢¤”…•:˜‰—^ž•¢¤”…’‰¢š™0™Pϒž§§•‡£L¢P”…’ž˜¢¤”…• ™,•’£“‡”

Ƥ•¤¨:’ž˜…[’…ž¢P”…• —…®L™,•¤¢—…©\¢—¢¤”…•±L£™¢“‡”šœ§Ä¬—žšœ˜¢,•…£L¢—¯•¤¢0¢¤”…•

m å

ZLD‡C*ep{€ro4Z

 ˯€’šœ˜¡™ šœÏ–šœ§’‡£L¢p— Å Ô7ÕÖT£••xšz˜‰™,•‡£œ¢ š—^˜x’ž§¯‡—G£/š¢¤”žÏ

 Ò7™,•…›…€—‡Õ“P—Gž•

 ÑE•P’£“‡”¡¢¤”…•:§•’©4˜‰—Gž•˜¢—„šœ˜‰™,•…£°¢ª¢P”…•–•‡˜¢¤£°¨

 ש˜š™ ˜‰—‡¢4©›ž§§¢P”…•…˜šœ˜‰™,•‡£œ¢4¢¤”…•:˜…•¤¦3•‡˜¢P£œ¨šœ˜¢p—:¢¤”…•–’G¬€¬£°—;¬‡£/š’‰¢•x¬ž§’…“•

 0¢P”…•‡£œ¦š™,• ™P¬ž§š¢˜Gýÿ•¤¢ ¬[­• ¢¤”…•:¬…’£•‡˜¢ ˜‰—Gž• —‡©0˜GþG©0­• ¢¤”…•±*£°™p¢“‡”šœ§

¬‡—Gšœ˜¢•‡£Tšœ˜[¬x’ž˜…¯‹­• ¢¤”…•:˜‰—Gž•–¯^£—^›ž¬„¬—žšœ˜¢,•P¢p—‹­¤¨¡©ý

 ! "#"$&%'()*+',)-.(/012)3

$4%

 +56/ !#"$&%2'37 #"$&%298:;"1

m

][C*AC^{žro4Z

 è@’ž˜…E§•„šœ˜¡’¡¦ƒ’P¨:™wšœÏ–šœ§’£5¢—„šœ˜‰™,•…£°¢wš—;˜

 ÿ‡’…Ç ¨ž•…§•¤¢ š—;˜–Õÿ‡—G“’¢,•¢P”…•–ž’¢,’x•‡˜¢¤£°¨þ*£•‡Ï—…Ì…•:š¢­ž›¢€—^˜ED¢

m º

eo4†@ACa?¾¿

å

ZLf*eCE>*D…CdrkZg?>4Fr/?_@? DGr‚;Coav:{žFLCdZLoƒK@C¼t4eoª_@¾K0_LC

{‰oIrkZLfaepC7>LD‡Cdr/Z¾fE>*f*FLC}A°r/ZLC¼Džrz‚^C}?ŠCE>ZLD?\oepC¼fEo4;~TrkZLt}oJvK>5{…>

rkZ¾f7>LD‡C¼oJvDG@Ar{

m

ˆ4oªAk_5{€rzoªZƒ¿|]‹r½TrzK@CÀ{žFLC¼faFTrkAKNZLoƒK@CEDŠr/Z5{‰oD…C;t4?ŠC*Z5{‰D;hD…{‰o@eCdrkZ

CE>*f*FZLoƒK@CdJoªr/Z5{‰C*eDŽ{‰oD…CEt4?\CaZ5{‰D$>ZLKo4Z@A~BfaFTrkAKNZLoƒK@CEDŠr/Z

÷:eCEC¼oavo@eK@Cae:S¾q$r{žFdSdD‡C;t4?ŠC*Z5{‰D

m

÷[q[od½*>Je rœ>@Z5{‰DŽoJvˆ

¹

ˆ–ôõö÷:eC;CT¿

m G rFaCEKˆrz‚^CBˆ4C;t4?\CaZ5{‰D

 Ñ^¢’£œ¢ ­¤¨¡±L§§šz˜‰¯x¢¤”…•:˜‰—Gž•P™šœ˜–¢P”…•±L£°™p¢™,•P¯^ϕ‡˜¢0¢ šœ§§Gš¢š™4©p›ž§§

 ֔…•‡˜¡±L§§¢¤”…•:˜‰—^ž•¤™šœ˜¡™•“P—;˜…[™,•¤¯;ϕ‡˜¢þ^¢¤”š™£k•PçE›šœ£•P™“¤—;¬¤¨€šz˜‰¯‹˜‰—Gž•¤™šœ˜

¢P”‡š™0™,•¤¯;ϕ‡˜¢—;˜ž§¨

m H

>aep~Tr/ZLtˆr‚;Cˆ4CEt4?\CaZ5{‰D

 ü…—ž£ª­ž›ž§Æ‡§—€’…7þG^š™p¢P£/šœ­ž›¢•¡˜‰—Gž•P™•¤Ì…•‡˜ž§¨:’Gϗ^˜‰¯¢P”…• ™,•¤¯;ϕ‡˜¢™

 –˜x•¤Ì…•‡£œ¨Ä˜…•¤¦˜‰—Gž•¡šœ˜‰™,•‡£œ¢wš—;˜Gþ^“‡£•’¢,•–’„˜…•¤¦3™•P¯;ϕ‡˜¢0©k—ž£J¢¤”…• ™,•P¯^Ï •…˜¢

¢—:¦”š“‡”¢¤”…•:˜…•¤¦˜‰—Gž•:­€•…§—;˜‰¯‡™

 Ö5—^›…“‡”…•P™—;˜ž§¨¡—;˜…•–™,•¤¯;ϕ‡˜¢šœ˜¡•’…“‡”šz˜‰™,•‡£œ¢’‰™—;¬ž¬‡—™,•¢p—¢¤”…•±GŸ‡•[™wšÇ•

m

ÄrztTC*exvepC4J0_LC*ZLf;~3oJvÄ?ŠC*?Šo@ep~3>AAoƒfE>L{€ro4Z3>@ZLKgK@CE>AAoƒfE>L{€rzoªZ

fE>AADŠrkZ

¹

ˆ–ôõö÷eC;CEDŠrDs>gaepo4†@AC*?

m

‹ZLoa{žFLCae>@@aeoT>*f*FrzDŽ{‰oIaeCGö‰>@AkAoƒfE>L{‰C3?ŠC*?Šo@ep~Bvwoe¡CaZ5{€rkeC

ZLoƒK@C¼tªeo4_@

m

ˆ*>LfECGö{€rk?ŠCÀ{že,>LK@CEoJŒ¿

 ¥T—Gž•–™P¬ž§š¢šœ˜[ü^›ž§§^‘aÑ Å Ô7ÕÖT£••xš™•¤Ø“‰š•…˜¢4¢P”…’ž˜[˜‰—ž£-ϒG§;‘*Ñ Å Ô7ÕÖT£••

m

ó:oƒK@CDžrz‚^C¾á

¹

>*f*FLC}ArkZLC¼Džrz‚^C5áÀiJWu†;~5{‰CED

m

=xC;~¾Džrz‚^C5á

º

oªr/Z5{‰C*eDžrz‚^C5á WI†;~5{‰CED

m G oe

¹

ˆ0ˆu{žeC;CED;¿sV5iI`žC^~LDÀJC*eÄZLoƒK@C

m G oeÐô

õ

ö÷epCECED;¿

å

Z5{‰CaePZ*>@AZLoƒK@C¼øI`žC;~LD^h-KdfaFTrkAKNToƒr/Z5{‰CaepD$>@ZLK

Z@_@?†TC*e:oavÐ`žC;~LD_LD…CEK

m G oe

¹

ˆ–ô¡õö÷epCEC;DE¿

å

Z5{‰Cae¤Z*>AZLoƒK@C}V7WI`GC^~LD^hMLeD‰{ŽfaFTr/AK<JoªrkZ5{‰Cae

m

÷|r/?\CÀvwo@e:SJOTO4=»D…C7>aepfaFLCED

ô õ ö÷epCEC;Ds>aeCd?\oepCÀ{žF*>Z3SJQO D^Ao5q[Cae¡{žF*>Z ˆ–ô õ ö÷:eC;C

m

ˆ4C;t4?\CaZ5{‰CEK

¹

ˆ–ô õ ö÷eC;C¼D…C7>aepfaF3D^Ao5q[C*ex{žF*>@Z

¹

ˆ–ô õ ö÷eC;C

†JCEfE>_LD…CT¿l†ae>ZLf*FTr/ZLtv >*f^{‰oexoav:vwo@eP?ŠC*e[rzDACED…D¼M€c3o@eCÀf7>LfaFLC

?¼rzD…D‡C;DX¼hC:F*{že,>¾fEo4?*>ae¤rD‡o4ZLDZLC;CEK@CEKg{‰of*F*oƒoJD‡Cde¤rt4F5{

m

ô–C;f7>@_LD‡C¼oJvÐA>*‚G~¾K@C*AC;{€ro4Z?\oTD‰{ŽoJvx{žFLC¼{€rk?ŠC3rzD|DGJCaZ5{\r/Z

Aoƒf7>5{€r/ZLtd{žF*CdepCEfEo@eKhD‡oK@C*AC;{‰C}JCaevwoe¤?>@ZLfEC¼DGrk?rkAz>ae¡{‰o

m ¹

ˆ–ô õ ö÷:eCEC;Ds>aeCŠq[oeD…C¼{žF*>@Zbô õ ö÷eC;CEDŽvwo@er/ZLD…Caep{€ro4Z†JCEf7>@_LD…C

oJvx{žFLC¼D^@A°r{Žf;oTD‰{

m ˆ ¹

ˆ–ô õ ö÷:eCEC;DeC;K0_LfECDG@Ar{‹fEoTD‰{ŽD…otªr½LC¾r/Z5{‰C*eP?\CEK4rœ>5{‰C

JCaevwoe¤?>@ZLfEC

m

ô–õö÷epCEC;DF*>5½LC{‰o>AAoƒfE>L{‰C¼>gZLCGqRQTS"UMVgo4ZBC^½LCaep~BD^@A°r{Äq$FTr/AC

_AA ˆ–ô õ ö÷epCEC;D$?Š>`žC>AAoƒfE>L{€rzoªZŠq\FLC*ZWQTS"UTVYX!ZS![-\brzDÄv_@AAP

m G _AA

¹

ˆ ô õ ö÷epCEC;Ds>aeCd†JC;{{‰C*e:{žF*>@Zbô õ ö÷epCECED\r/Z3>@AkAƒ>*DGJCEf^{‰D

C:FafEC*5{Žvwo@e¡D^*>LfEC

m å

ZgA°r/?¼r{‰CEKgD^*>LfEC¼CaZ5½Trkeo4Z@?\CaZ5{

¹

ˆ–ôõö÷:eC;CEDs>@ZLKˆ4C;t4?ŠC*Z5{‰CEK

¹

ˆ–ô

õ

ö÷:eCEC;DaepoJ½TrzK@Cv >*D‰{‰CaexD…C7>aef*FLCEDŽq\FTrkAC¼D…{€rkAkA†JC*rkZLtg>†@AC

{‰oDG_@@Joe{\r/ZLf*eCa?\CaZ5{…>@A_@JK>L{‰C;D

m

ˆ_Tr{…>†@ACÀvwoex>@@A°rzfE>L{€rzoªZLDA°r/`žC}]‹rztªr{…>AArk†ae,>ae rzCED^h-]ÀZ@A°r/ZLC

m cd>Tr/Z

º

epo4†@AC*? ô–C*rkZLtdK@K0eC;D‡D…CEK¿`_aQMbdcfehgZeji9k4lS!QfSjgmU-e'kne

k4ZeQ)opgVZZ*V)UqknSri;eji)sjVtldou[jonV;g?[Mb"gSZvkwsjVtx"[jVZc

m å

AkAöC;ŒCEf^{‰D|f7>@_LD‡C;K<†;~B{žFLCdaepo4†@AC*?3¿

 y\’‰™p¢,’‰¯€• —‡©0­…’G˜…¦š¢¤”

 Ò^—;§§›¢ šœ˜¯x¢¤”…•–“’…“‡”…•

m

c3oTD‰{ÄqsrzK@C*A~g_LD‡C;KÍóxö‰>ae~¾ˆª{‰oe>*tTC}c3oƒK@CaAMóˆ–cdXŽD…{‰o@eC;D

epCaAz>5{€rzoªZ'{DeC;fEo@eK@DsD…C4J0_LC*Z5{€rœ>@AkA~r/Z¾DGAoJ{{‰C;KbK4rD^`d*>LtTCED

m

ˆ0>@?@AC}|_LCaep~ƒ¿

m

D…CaACEf^{ÀZ*>@?\CÀveo4? Á<q$FLCaeCB>LtTCW~ W@O

m

ÁCaAz>5{€rzoªZbÁòfEo4Z5{…>Tr/ZLDŽ{žF@epCECB>5{{Ge r/†@_5{‰C;D$ˆ0ˆ óÐh¡ó>?\CB>@ZLKgtTC

m G

oe¡{žFLC>†JoJ½LCJ0_LC*ep~B{žFLCóˆ–cÂ?ŠoƒK@C*AF*>*D\r/Z5vwCae rzo@exf7>LfaFLC

j jƒ‚

m G

_AA~¾K@C;fEo4?JoTD…CEKvwo@eP? oJv

H

C*ep{€rzfE>A

º

>aep{€r{€rzo4ZTrkZ*t

m º

>aep{€r{€rzo4ZLDs>@ZgZ7ö>L{{že r/†@_5{‰CdeC*Az>5{€rzo4Zr/Z5{‰oIZ¾D^_@†7öeCaA>L{€ro4ZLD

m „

>*f*F3DG_@†7ö€epCaA>L{€rzoªZ¾fEo4Z5{…>Tr/ZLDŽ{ qo>5{{že¤rk†@_5{‰CED;¿Ä>gAoTtªrf7>@AeC;fEo@eK

rK>ZLK}{GFLC>5{{že¤r/†@_5{‰CÀ½*>A_LC

m

ˆ_@†7öeC*Az>5{€rzo4ZLDs>aepC¼D‰{…o@eC;Kb>*DŠeCEtª_@Az>ae„epCaAz>5{€rzo4ZLDŠrkZ¾D^AoJ{{‰CEK

*>LtTCED

m

KT½*>@Z5{…>LtTCED;¿

 胚¯;”:€•P¯;£••–—‡©@™P¬…’¢ š’ž§E§—^“P’G§š¢-¨–©/—ž£J™,•çE›…•‡˜¢wš’ž§ž’…““•¤™™—‡©’G˜x’¢p¢¤£lšz­ž›¢,•

 Å

•¤¢¢,•‡£ª×…?g’ž˜…Ä‘a’…“‡”…•:¬€•‡£œ©k—G£-ϒž˜…“•

m

]‹rD>LKT½*>Z5{…>LtTCJ¿

 Ò;•‡£œ©/—ž£-ϒG˜…“P•¡™ š¯;˜š±;“’ž˜¢P§¨¡ž•¤¢,•…£lš—G£’¢,•¤™0©/—ž£TçE›…•‡£/š•P™šz˜Ì‰—;§Ìšœ˜‰¯ÄÏ¡›ž§¢wšœ¬ž§•

N N ‡†ˆ‚

m å

K@C7>rDŽ{‰ou`žCEC*3{žFLC>5{{že¤r/†@_5{‰CÀ½*>A_LCEDŽoJvCE>*f*FeC;fEo@eKo4Z{žF*C

D‡>?\Cd*>*tJC>LDŠr/Zgóˆ–c q$FTr/ACd_LDžr/ZLtg>¾f7>LfaFLCGöve rzCaZLK0A~

>@AtTo@e¤r{žF@?àvwoe[@Az>Lf*rkZ*td{žFLCa? r/ZLDžrzK@CÀ{žFLCd*>*tTC

m H

Cae{€rzf7>@AkA~*>aep{€r{€ro4ZgeC;fEo@eK@DŽqsr{žFTrkZ*>LtTCJh0D‰{‰oe¤rkZLt}{‰oTtTC^{GFLC*e

½*>@Ak_LC;D|oJv:C7>LfaF3>L{{že r/†@_5{‰CdrkZ3>g?rkZTr/*>LtTC

m

KT½*>@Z5{…>LtTCED;¿



ϒŸ€šœÏ–šÇ•P™šœ˜¢•‡£œÕ £•“¤—G£™P¬…’¢ š’G§;§—G“’ž§š¢-¨–¢P”ž›‰™šœÏ¡¬‡£°—‡Ìšœ˜‰¯“’…“‡”…•

¬•‡£œ©/—ž£-Ï ’ž˜…“•

 ϖšœ˜šœÏ’ž§;£•“P—ž£|£•“¤—;˜‰™p¢¤£É›…“ ¢ š—^˜:“P—‡™p¢

 —ž£œ¢P”‰—‡¯—;˜…’ž§€¢—:—‡¢P”…•…£Jž•P™wš¯;˜¡ž•“‰š™ š—;˜‰™0’…™š¢4’‰®*•P“¤¢™0—^˜ž§¨¢P”…• ž’¢,’–¦š¢¤”šœ˜

’„¬…’‰¯€•

÷sFLCÀvwoªAkAo7qsr/ZLt}DGArzK@C¼DGFLo5qÐD|{žFLC¼f7>LfaFLCd†TC*F*>L½Tro4_@e¡oJv

º

Š‰

m G

oexD‰{‰oe¤rkZLtg>geCaA>L{€ro4Z¾oJv:KC;t4epCEC}Zh

º

Š‰´*>aep{€r{€rzo4ZLDŽ{žFLCd*>LtTC

rkZ5{‰ouZg?rkZTr/*>LtTCED

m º

>LtTC}Ã:C7>LK@CaexfEo4Z5{…>Tr/ZLDJoªr/Z5{‰C*eDŽ{‰ou†JCEtªrkZTr/ZLtoavC7>LfaF

?¼r/ZTrka>LtTCahZ@_@?†TC*eoJvx>L{{že r/†@_5{‰CED^h4{žFLCÀ>L{{že r/†@_5{‰CDžrz‚^CED^hf*_@ePeC*Z5{

Z@_@?†TC*e:oavÐepCEfEo@eK@DsoªZB{žFLC}*>LtTC¼>ZLK}veCEC¼DG*>*f;CB>L½*>Tr/A>†@AC

m G rFaCEKNACaZLta{žFd>5{{že¤r/†@_5{‰C;D$>aeC¼D‰{‰oepCEKNr/Z

G

ö?rkZTr/*>LtTCEDnP[÷sFLC¼C*ZLK

oJv

G

ö€?¼r/ZTrk*>*tTC3F*>LDaepCED…CaZLf;Cg†Tr{нLCEf;{‰o@e

m H

>ae¤rœ>@†@ACdACaZLtJ{žF3>L{{že r/†@_5{‰C;D$>aeC¼D‰{‰oepCEKNr/Z

H

ö?rkZTr/*>LtTCEDnP

m

ô_@A`^öAo@>LK4r/ZLt}>ZLK

å

ZLD…Cae{€rzo4ZLD

 ˧§—G“’¢,• •’…“‡”„Ï–šœ˜šœ¬‰’…¯•—;˜¡¢¤”…•:¬…’…¯•­…’‰™,•—;˜:’¢p¢¤£/šœ­ž›¢,•Ì…’G§›…• ™ šÇP•

 ×z˜‰™,•‡£œ¢p™£k•P“P—ž£€™­P¨:“¤—;¬P¨šz˜‰¯[’…“¤¢¤›…’G§Ì…’ž§›…•¢p—[•’…“‡”[ϖšœ˜šœ¬…’‰¯€•

 y¾”‰•‡˜Ì…’£/š’ž­ž§•§•‡˜‰¯‡¢¤”Ì…’G§›…•P™4’£•¡¬‡£•P™,•‡˜¢Pþ7Ϛz˜šœ¬…’‰¯€•–­—^›ž˜…ž’£/š•P™˜…•P•x¢p—

­•’…‹,›‰™p¢,•P¢p—[’…““P—^ϗ^ž’¢,•£•“¤—G£€™’‰™0¢P”…• ¨:’£•xšœ˜‰™,•…£°¢•Äšœ˜–¢P”…•:¬…’‰¯€•

 ҇ˌ3“’ž§“‡›ž§’¢•P™ª¢P”…•:¬‡—™ š¢wš—;˜—‡©•’…“‡”:’¢p¢¤£/šœ­ž›¢,•Ì…’G§›…• —‡©T¢P”…•:¬…’‰¯€•‡þ

™p¢p—ž£k•¤™¢¤”…•Ì…’G§›…•–’G˜…Ð›ž¬€ž’¢,•P™ª¢P”…•:­š¢¤Ï’G¬‰™0’ž˜…—‡®L™•¤¢’£-£’P¨‰™

’ž¬ž¬£°—;¬‡£/š’¢,•‡§¨

m

Y[JK>L{€ro4ZLD

 ü^šœ˜‰¢¤”…•:¬—‡™ š¢ š—;˜—‡©T¢P”…•–’¢p¢¤£lšz­ž›¢,•Ì…’G§›…•—‡©T¢P”…•:£•“P—ž£Ä’ž˜…¢¤”…•‡˜

›ž¬ž’‰¢•¢¤”…•Ì…’G§›…•

 檬ž’¢,•P™4¢p—Ì…’£/š’ž­ž§•x§•‡˜¯‡¢P”–Ì…’G§›…•P™–Ï’P¨„£•çE›šz£k•xϚz˜šœ¬…’‰¯€•x§• Ì…•‡§

£•P—ž£°¯€’ž˜šÇ’¢ š—;˜‰™

 ש@¢¤”…• ™P¬…’…“•xš™ ˜‰—‡¢0™P›Ø“‰š•‡˜¢4¢—’‡“P“P—;ϗGž’¢,•’G˜‰‹£k• Õ—ž£°¯€’ž˜šÇP’‰¢wš—;˜:š™

m

][C*AC^{žro4Z

 ¥@Ñ9z8›‰™•P™™¤§—‡¢’£-£’P¨x¢p—‹Ï’£-ƒž˜x•‡˜¢P£œ¨:’‰™ž•‡§• ¢,•

 ҇ˌƤ••‡¬‰™ª¢P£’…“‡Æ —…©ž•…§•¤¢,•PÐ£•“¤—G£€™–›‰™wšœ˜‰¯’[­š¢¤Ï’G¬’¢ª¢¤”…•™p¢,’£œ¢4—‡©J¢P”…•

¬…’‰¯€•’ž˜…‹›‰™,•¤™­š¢-¦š™•–“’ž§“‡›ž§’‰¢wš—^˜‰™ª¢—:±L˜…¦”…• ¢P”…•‡£J’„£•“P—ž£Ðš™€•‡§•¤¢•

 äL•P—ž£°¯€’ž˜šÇP’‰¢wš—;˜x“P’G˜[­€•–€—;˜…•¦š¢P”šz˜Ï–šœ˜šœ¬…’‰¯€• ’©k¢•‡£Jž•‡§•¤¢wš—;˜™p—„’‰™0¢—

ϖšœ˜šœÏ–šÇ•©£k’‰¯;ϕ‡˜¢,’¢ š—^˜

m óˆ–c

H D º

Š‰

å

?B*>Lf;{‹o4ZBf7>LfaFLC}†JC*Fa>5½Trzoª_@e

 ҇ˌg£•E›…“•P™ž’¢,’[¬•‡˜…’ž§¢-¨x’¢ ­—…¢P”x“’…“‡”…•:§•¤Ì…•‡§™ÿE¡’ž˜…Žÿ‘’ž˜…

£•E›…“•¤™™¢,’ž§§¢ šzÏ •

 ֔š™–£•E›‰“¤¢ š—^˜šœ˜˜ž›žÏ¡­€•‡£*—…©Ï–š™™•P™£•P™¤›ž§¢™šœ˜©›ž£œ¢P”…•‡£ƒ£•E›…“¤¢wš—;˜—‡©

óˆ–cˆ“

º

Š‰Úˆ4C*ZLDGr{€r½Tr{¤~¾‹Z*>@A~LDžrzD

m

|_LCae~3C:FaCEf*_5{€rzo4Z¾{€rk?ŠC¼oJvÐóˆ–c >@ZLK

º

Š‰&f;o4Z5½LC*etTC>*D‹{žFLC

Z@_@?†TC*e:oavЏaepo:”CEf^{‰CEKb>L{{že r/†@_5{‰CEDŠr/ZLfaepC7>LD‡C

m

DŽ{žFLC¼K@CEt4epCECoJvÄeC*Az>5{€rzo4Zr/ZLf*eCE>*D…CEDsoJ{žFLCae¡v >Lf;{‰o@eD|DG_LfaFd>LD

„ å

>*f*FLC Caevwoe¤?>@ZLfEC

m å

Z3>¾K@C*?>@ZLKJöK0e r½LCaZ•J0_LC*ep~¾CEFaC;fa_5{€ro4Z@Az>@Z¾f*FTr/AKgo4JCae>L{‰o@e

epC;{ž_@ePZLDsf;o4Z5{žeoªA{‰ou*>aeCaZ5{‹o4JCae>L{‰o@e[r/??ŠC;K4rœ>5{‰CaA~3>5v,{‰Cae

tTC*ZLCae>L{€rkZLtgoªZLCÀ{ž_@@AC

m

ˆ4od{žFLCoªTC*e,>5{‰oexC:FaCEf*_5{€rzo4Z3D…C4J0_LC*ZLfEC}rzDŠAr/`žC

{

º¡¹º¹º¹º¹º¹º¡¹º P–P#{

m å

ZLD…{že¤_Lf;{€ro4Z3f7>LfaFLCÀ{žF@e,>LD^FTrkZLtf7>@Z¾oªf;fa_@eq$FLCaZ¾{žFLC¼fEo4?†Tr/ZLC;K

Džrz‚^CoJvx{ q[oo4JCae>L{‰o@eD|CEFaf;CEC;K@Ds{žFLC¼Džrz‚^CoJv:{žFLC¼DG?>@AkACED‰{Gh

m n r½LCaZ3>•J0_LCae~Eh>*K@Kg>¾D^JCEfLrœ>@A†@_5ŒCaexo4JCae>L{‰o@e:>L{ÐfEC*ep{…>@rkZ

@A>*f;CED\†TC^{ q[C;CaZ3>}*>aeC*Z5{Ðo4JCae>L{‰o@e“aoªTC*e,>5{‰oetªeo4_@B>@ZLK}f*FTr/AK

o4JC*e,>5{‰oe“*o4JCae,>5{‰oe¡t4eoª_@

m

ô_5ŒCaexoªTC*e,>5{‰oe:>@†JoJ½LCÀfaFTrkAKNF*>*D|>Z¾>Je¤e,>;~BoJvďToƒr/Z5{‰CaepD|{žF*>5{

JoªrkZ5{Ð{‰oIr/Z5{‰C*eP?ŠC;K4rœ>5{‰C}eCEDG_@A{‹{ž_@@AC;D

m

÷sFTrzDŽC;ŒCEf^{€r½LC*A~3f*F*>ZLtTC;D|{žFLC¼C:FaCEfa_5{€ro4Z3D…C4J0_LCaZLf;C{‰o

{

º¡¹x¹x¹:¹x¹ºxº:ºxºxº¡¹x¹:¹:¹:¹º:ºxº:ºxº P˜P˜{

m

÷sFLC¼C:FaCEf*_5{€rzo4Z3D…C4J0_LC*ZLfECBDGFLo5qÐD|{žF*>5{\Z@_@?B†JCaexoJv„r/ZLD‰{žeP_Lf;{€ro4Z

fE>*f*FLC}?¼rzD…D‡C;D$K@C;faepC7>LD‡CBDG_@†LD‰{…>Z5{€rz>AkA~

m

÷sFLCdepCEK0_Lf;CEKbfE>*f*FLC}?¼rzD…D‡C;D\>aepC¼K0_LCÀ{‰oIr/?aeoa½LCEKur/ZLD‰{žeP_Lf^{€rzo4Z

m n r½LCaZ3>•J0_LCae~gA>Z}rzK@C*Z5{€rv,~B{žFLC¼CEFaC;fa_5{€rzo4Z¾t4eo4_@LD‹{žF*>L{Ž>aeC

fE>ZLK4rK>L{‰Cd_@ZTr{‰DŽvwo@e[†@_LŒC*e¤r/ZLt

m

K@K>gZLC^q#C:Fƒ@ArzfLr{\†_5ŒCae r/ZLto4JC*e,>5{‰oe:>@†Toa½LC{žFLCC:FaCEf*_5{€rzo4Z

t4epo4_@hrvÄZ*C;fEC;D‡D‡>aep~

m å

?B@ACa?\CaZ5{…>5{€rzo4Z¾oJvĆ@_5Œ C*e:oªTC*e,>5{‰oe¿

 Ñ*›€¬ž¬—ž£œ¢™0—^¬€•‡˜Õw˜…• Ÿ‰¢Õ“‡§—™•¡šœ˜¢,•…£°©/’‡“P•

 zx’€šz˜¢,’šœ˜‰™ª¢-¦@—™p¢,’¢,•P™@™;y¾”…• ¢P”…•‡£a•‡˜…Õɗ‡©Õ-¢P›ž¬ž§•¤™š™ £k•P“•‰šÌ…•P©p£°—;Ïg¢P”…•

“‡”šz§—^¬€•‡£’¢—ž£T’ž˜…Šy¾”…• ¢P”…•‡£Tš¢™ ­ž›®*•‡£•¢¤›ž¬ž§•P™”…’‰Ì…•:­€••…˜:“¤—;˜‰™P›žÏ•

 zx’€šz˜¢,’šœ˜‰™0’ž˜x’£-£k’¤¨:—…©¬‡—Gšœ˜¢•‡£°™4¢—:¢P›ž¬ž§•¤™4¢¤”…’‰¢0’£•–™p¢p—ž£k•P‹šœ˜¡“‡”šœ§

—;¬•‡£’¢—ž£˜D™™P¬…’…“•

m

ô–C*ZLCnLƒ{‰DsoJvІ@_5ŒCaexo4JC*e,>5{‰oe¿

 ×z˜…“‡£•’‰™,•:šœ˜¡çE›…•‡£œ¨¡¢P”ž£°—;›‰¯^”ž¬ž›¢0E›…•¢p—[ž•“‡£•’‰™,•xšœ˜šz˜‰™p¢P£-›…“¤¢wš—;˜“’‡“…”…•

ϖš™™,•¤™

m

‹AAƒo4JCae>L{‰o@eD|K@o4Z'{œ{\†TC*ZLCnLƒ{Žvepo4? †@_5Œ C*e¤r/ZLtC P°tTP[D^?Š>AA

fE>JepK4r/Z*>@Ar{¤~¾oªTC*e,>5{‰oepD;h–†@Aoƒf*`*rkZLto4JCae,>5{‰oepDAr/`žC¼D…oe{

m

÷sFLCd@A>*f;Ca?\CaZ5{ŽoJvІ@_5ŒCaexo4JC*e,>5{‰oeDŠrkZ3>•J0_LCaep~g@A>Z¾fE>Zg†JC

K@o4ZLC3†;~g_LDžr/ZLtg>g†JoJ{{‰o4?sö€_@a>LD…D|oJv:{žFLCd@Az>@ZB{žepCEC

m

÷sFTrzDŠFLo5q[C^½LCae„ZLCEC;K@DsD‡oª?ŠCd?ŠC;faF*>@ZTrzDG? oJv:CED‰{€r/?Š>L{€rkZLt{žFLC

m

^C3Aoƒo4`žCEK>5{Ð{žF@eC;CB>@aepoƒfaFLC;D|vwo@e[rk?BaepoJ½Tr/ZLt}fE>*f*FLC

JCaevwoe¤?>@ZLfEC

m ¹

ˆ–ôõö÷:eCEC¼>@*eo@>LfaF¼q„>*Ds>@†@AC{‰otªr½LCd†JC;{{‰C*e:D‡CE>JepfaF

JCaevwoe¤?>@ZLfECq\FTrkAC>L{Ä{žFLCD‡>?\CÀ{€r/?\CB>@AkAo5qsr/ZLtbrkZ*f*eC*?ŠC*Z5{…>A

_@JK>L{‰C;D

m º

Š‰Ú>@*eo@>LfaFBfaF*>ZLtJCEK{žFLCK>5{…>gAz>;~Eoª_5{$?ŠoƒK@CaA@{…o}CaZLDG_@eC

{žF*>5{‹f7>LfaFLCDG*>LfECdrD|oƒfEf*_@TrzC;K͆^~g_LD…C;v_@AƒK>L{…>3>@ZLKur{|>@AD…o

epCa?Š>@rkZLCEKo@ep{žFLoTtToªZ*>AT{‰ooJ{žFLCaexK@CEDžrztªZ3K@CEfLrzDžrzo4ZLD

m

ô_5ŒCae r/ZLt>@aepo@>LfaF{že¤rCEKg{‰o}D…o4A½LC{žFLCdaepo4†@AC*? oJv„r/?aepoJ½Tr/ZLt

rkZLD…{že¤_Lf;{€rzoªZdfE>*f*FLC}JCaevwoe¤?>@ZLfEC¼vwo@e¡K@Ca?Š>ZLKJöK0e r½LC*ZgTr/JCaA°r/ZLCEK

m š

_@ZbÁ>*o0h =:C*Z@ZLC;{žF3vPÁoTD…D;¿scd>`Lr/ZLtf›

õ

ö÷epCEC;D

¹

>LfaFLC

¹

o4ZLD…f*rzoª_LDr/Zbcd>Tr/Zc3C*?Šo@ep~4P[ˆ

ån cˆ]À]

¹

o4Z5vwC*eC*ZLfEC¾SJOTOTO0¿

W@øaQaöW;KTi

m

‹Z*>LD‰{…>*D…DGrz>dÄr/Az>@?>@`Lrlh]„>5½TrzK

š

P ][Cp^(r{{Gh¡cd>aeP`d]mP–ÃÄrkAkAkh

cd>ae¤roTD|ˆ`žo4_@Z*>@`LrzD;¿œ^C7>5½Tr/ZLtuÁC*Az>5{€rzo4ZLD‹vwoe

¹

>LfaFLC

º

Caevwoe¤?>@ZLfEC P

H

Hƒ]sôâSTOTO4VT¿ÉV5iJU*öžV&KTO

m š

r/ZLtªeCaZW:FLoª_h–=:C*Z@ZLC;{žF3vPÁoTD…D;¿$ô_5ŒCae r/ZLtu]„>L{…>@†*>*D…C

]JCae,>5{€rzoªZLDŽvwoe

„

Z@F*>@ZLfECEK

å

ZLD‰{žeP_Lf^{€rzo4Z

¹

>*f*FLC

º

C*epvwoe¤?>@ZLfEC P

ˆ cˆ]À] o4Z5vwCaepCaZLf;C¾STOJOJW¿-V5U4V;öSTOTS