ДБС-дегі кері индекс стратегиясы: мәліметтерді жылдам іздеу үшін кілт мәндерін кері аудару. Монотонды өсетін деректерге арналған тиімді шешім. Индекстеу, ДБС, өнімділік.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Деректер қорын индекстеудің кері стратегиясы
Кері индекс (DBMS)
Reversing strategy for database indexing
Reverse Index (DBMS)
Деректерді басқару жүйелері әртүрлі қолданбаларда өнімділікті және деректердің сақтығын жақсарту үшін түрлі индекс түрлерін ұсынады. Индекс түрлеріне b-ағаштар, биттік карталар және r-ағаштар жатады. Деректерді басқару жүйелерінде кері кілт индексі стратегиясы кілт мәнін индекске енгізер алдында керітеді. Мысалы, 24538 мәні индексте 83542 болып өзгереді. Кілт мәнін керіте беру, әсіресе, әрбір жаңа кілт мәні алдыңғысынан үлкен болатын, яғни мәндер монотонды түрде өсетін реттік нөмірлер сияқты деректерді индекстеу үшін тиімді. Кері кілт индекстері жоғары көлемді транзакцияларды өңдеу жүйелерінде ерекше маңызға ие, себебі олар индекс блоктарына талас тудыруды азайтады.
Database management systems provide multiple types of indexes to improve performance and data integrity across diverse applications. Index types include b trees, bitmaps, and r trees. In database management systems, a reverse key index strategy reverses the key value before entering it in the index. E. g., the value 24538 becomes 83542 in the index. Reversing the key value is particularly useful for indexing data such as sequence numbers, where each new key value is greater than the prior value, i. e., values monotonically increase. Reverse key indexes have become particularly important in high volume transaction processing systems because they reduce contention for index blocks.
Деректерді құру
Кері кілт индекстері b ағаш құрылымдарын пайдаланады, бірақ кілт мәндерін енгізу алдында алдын ала өңдейді. Тұрақтандыру үшін, b ағаштары ұқсас мәндерді бір индекс блогына орналастырады, мысалы, 24538 және 24539 бір блокқа сақталады. Бұл оларды нақты мәнді іздеуде де, белгілі бір диапазон ішіндегі мәндерді табуда да тиімді етеді. Дегенмен, егер қолданба мәндерді тізбекпен енгізсе, әрбір енгізу жаңа мәнді қосу үшін индекстегі ең соңғы блокқа қол жеткізуі керек. Егер көптеген пайдаланушылар бір уақытта енгізуге тырысса, олардың барлығы сол блокқа жазуға тырысып, кезекке тұруға мәжбүр болады, бұл қолданбаның жұмысын баяулатады. Бұл мәселе кластерленген деректер базаларында ерекше айқын болады, онда блок келесі пайдаланушының енгізуін жүзеге асыруына мүмкіндік беру үшін бір компьютердің жадынан екіншісіне көшірілуі мүмкін. Кілтті кері аудару ұқсас жаңа мәндерді бір жапырақ блокке шоғырландырудың орнына, бүкіл индекс бойынша таратып береді. Яғни, 24538 14538-мен бір блокқа, ал 24539 басқа блокқа түседі, бұл қақтығыстың себебін жояды. (14538, 24538-ден бұрын жасалғандықтан, олардың енгізілуі бір-біріне кедергі келтірмейді.)
Reversed key indexes use b tree structures, but preprocess key values before inserting them. Simplifying, b trees place similar values on a single index block, e. g., storing 24538 on the same block as 24539. This makes them efficient both for looking up a specific value and for finding values within a range. However, if the application inserts values in sequence, each insert must have access to the newest block in the index in order to add the new value. If many users attempt to insert at the same time, they all must write to that block and have to get in line, slowing down the application. This is particularly a problem in clustered databases, which may require the block to be copied from one computer's memory to another's to allow the next user to perform their insert. Reversing the key spreads similar new values across the entire index instead of concentrating them in any one leaf block. This means that 24538 appears on the same block as 14538 while 24539 goes to a different block, eliminating this cause of contention. (Since 14538 would have been created long before 24538, their inserts don't interfere with each other.)
Сұрау салу деректері
Кері индекстер нақты мәндерді табу үшін кері емес индекстердей тиімді, бірақ олар диапазондық сұраныстар үшін көмектеспейді. Диапазондық сұраныстар реттік нөмірлер сияқты жасалма мәндер үшін сирек кездеседі. Индекс бойынша іздеу кезінде сұраныс процессор ізделіп жатқан мәнді іздеуден бұрын керітеді.
Reverse indexes are just as efficient as unreversed indexes for finding specific values, although they aren't helpful for range queries. Range queries are uncommon for artificial values such as sequence numbers. When searching the index, the query processor simply reverses the search target before looking it up.
Деректерді өшіру
Әдетте, қосымшалар жаңа деректерді өшірмес бұрын орташа есеппен ескі деректерді өшіреді. Сондықтан, кіші реттік нөмірлері бар деректер, әдетте, үлкен мәндері бар деректерге дейін өшіріледі. Уақыт өте келе, стандартты b-ағаштарында кіші мәндерге арналған индекс блоктарында азын-малы мәндер қалады, соған сәйкес бос орын көбейеді, бұл "шірік" деп аталады. Шірік тек орынды ғана ысыраптап қоймайды, сонымен қатар сұраныс жылдамдығын төмендетеді, себебі шіріген индекс блоктарының аз бөлігі бір уақытта жадқа сыяды. b-ағашында, егер 14538 саны өшірілсе, оның индекс орыны бос қалады.
Typically, applications delete data that is older on average before deleting newer data. Thus, data with lower sequence numbers generally go before those with higher values. As time passes, in standard b trees, index blocks for lower values end up containing few values, with a commensurate increase in unused space, referred to as "rot". Rot not only wastes space, but slows query speeds, because a smaller fraction of a rotten index's blocks fit in memory at any one time. In a b tree, if 14538 gets deleted, its index space remains empty.