Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>Bear with me, this will take awhile :-).</p> <p>Think of a simple address book where you just add records on the end as new friends or colleagues arrive (the next entry would go at 5):</p> <pre><code>1. Bob Smith, 7 Station St, Wotahole, NJ 2. Greg Jones, 3 Railway Pde, Boot Hill, KA 3. Allan Brown, 27 Carriage Court, Washington, DC (home) 4. Allan Brown, 1066 Hastings Street, Washington, DC (work) 5. </code></pre> <p>Now you need to find someone's address. No trouble, I hear you say, just scan the list looking for the name, then read off the address.</p> <p>Now, what if you're so stunningly popular that you have 1,024 friends like me (I'm such a geek, I only allocate friends in powers of two - I actually have 2,024 but 1,000 of them are being held in limbo unitl I can get another 24 together :-).</p> <p>In order to find a particular friend, you'd have to scan, on average, 512 entries (half of those in use). That's quite tedious. The worst case is scanning all 1,024 of them to find the last person you added.</p> <p>Now let's add that index. Every time you add a new friend/colleague (or delete them if they cause you too much trouble), you update this index which stores just the name in sorted order along with the line number of the full entry (the index pages in your address book are magic and auto-sort everything you write in them).</p> <p>The index for out mini-list above would be:</p> <pre><code>1. Allan Brown, 3 2. Allan Brown, 4 3. Greg Jones, 2 4. Bob Smith, 1 </code></pre> <p>The names and line numbers take up less space than the full entries but the most important aspect is this.</p> <p>In order to find an entry, you only have to scan, worst case, 10 entries (log<sub>2</sub>1024). First, you check index number 512. If the name you're looking for is greater than that, you only have to look at entries 513-1024. If it's less, you're now only interested in entries 1-511. In either case, you've immediately cut down your search space by half.</p> <p>With the original method, you can only discard the one you check since you don't have the ordering information available to you.</p> <p>So the size of the search space goes like this (I've actually used powers of two for the indexed method but it's slightly better than that):</p> <pre><code>+-----------+----------------+------------+ | Iteration | Indexed method | Old method | +-----------+----------------+------------+ | 0 | 1024 | 1024 | | 1 | 512 | 1023 | | 2 | 256 | 1022 | | 3 | 128 | 1021 | | 4 | 64 | 1020 | | 5 | 32 | 1019 | | 6 | 16 | 1018 | | 7 | 8 | 1017 | | 8 | 4 | 1016 | | 9 | 2 | 1015 | | 10 | 1 | 1014 | +-----------+----------------+------------+ </code></pre> <p>Once you've found the index, extract the line number from it and, because you know you've got 16 entries per page, entry number 275 (for example) is on page 18, line 4. You can go straight there without further searching.</p> <p>So, at the cost of a little more storage space and some time maintaining the index, you've <em>greatly</em> increased the speed of your searches. And that's what indexes do in databases as well.</p>
    singulars
    1. This table or related slice is empty.
    1. PODatabase Indexes
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USpaxdiablo
    1. USpaxdiablo
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PODatabase Indexes
      singulars
      1. PTQuestion
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. This table or related slice is empty.
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload